[Nexus One Themes and Apps] Treatcon:
Tried another way, been doing a lot of reading.

adb pull /system/app/Contacts.apk

Open Contacts.apk with 7zip and extract to a folder named Contacts

Replace said png file with new version

Highlight all contents of the Contacts folder and 7zip using "Store" mode in zip

Rename zip extension to apk

zipalign -f 4 Contacts.apk NewContacts.apk

adb remount

adb push NewContacts.apk /system/app/Contacts.apk

adb reboot

After reboot still not working. Phone and Contacts are uninstalled completely.

Logcat start when I pushed the apk:

D/PackageManager( 113): Removing package com.android.contacts
D/PackageManager( 113): Services: com.android.contacts.util.EmptyService
D/PackageManager( 113): Activities: com.android.contacts.TwelveKeyDialer com.android.contacts.RecentCallsListActivity com.android.contacts.DialtactsActivity com.android.contacts.DialtactsContactsEntryActivity com.android.contacts.DialtactsFavoritesEntryActivity com.android.contacts.ContactsListActivity com.android.contacts.ContactsListActivity$JoinContactActivity com.android.contacts.ui.DisplayGroupsActivity com.android.contacts.ui.ShowOrCreateActivitycom.android.contacts.ui.QuickContactActivity com.android.contacts.ContactShortcut alias.DialShortcut alias.MessageShortcut com.android.contacts.CallDetailActivity com.android.contacts.ViewContactActivity com.android.contacts.ui.EditContactActivity com.android.contacts.ContactOptionsActivity com.android.contacts.AttachImage com.android.contacts.ContactsLiveFolders$AllContacts com.android.contacts.ContactsLiveFolders$StarredContacts com.android.contacts.ContactsLiveFolders$PhoneContacts com.android.contacts.ImportVCardActivity com.android.contacts.ExportVCardActivity com.android.contacts.ContactsPreferences
D/ActivityManager( 113): Uninstalling process com.android.contacts
D/ActivityManager( 113): Force removing process ProcessRecord{463072e0 214:android.process.acore/10022} (android.process.acore/10022)
I/Process ( 113): Sending signal. PID: 214 SIG: 9
W/ResourceType( 113): Resources don't contain package for resource number 0x7f080000
W/ResourceType( 113): Resources don't contain package for resource number 0x7f020047
W/ResourceType( 113): Resources don't contain package for resource number 0x7f020048
W/ResourceType( 113): Resources don't contain package for resource number 0x7f050000
W/ResourceType( 113): Resources don't contain package for resource number 0x7f020005
W/ResourceType( 113): Resources don't contain package for resource number 0x7f020004
W/ResourceType( 113): Resources don't contain package for resource number 0x7f0700e5
W/ResourceType( 113): Resources don't contain package for resource number 0x7f020031
W/ResourceType( 113): Resources don't contain package for resource number 0x7f020030
W/ResourceType( 113): Resources don't contain package for resource number 0x7f050000
I/ActivityManager( 113): Start proc com.android.vending for broadcast com.android.vending/.PackageMonitorReceiver: pid=561 uid=10008 gids={3003}
D/ActivityManager( 113): Received spurious death notification for thread android.os.BinderProxy@463134e8
D/dalvikvm( 186): GC freed 6988 objects / 381896 bytes in 232ms
I/ActivityThread( 561): Publishing provider com.android.vending.SuggestionsProvider: com.android.vending.SuggestionsProviderI/ActivityManager( 113): Start proc com.android.voicedialer for broadcast com.android.voicedialer/.VoiceDialerReceiver: pid=569 uid=10019 gids={3002}
D/VoiceDialerReceiver( 569): onReceive Intent { act=android.intent.action.PACKAGE_REMOVED dat=package:com.android.contacts flg=0x20000000 cmp=com.android.voicedialer/.VoiceDialerReceiver (has extras) }
D/PackageParser( 113): Scanning package: /system/app/Contacts.apk
I/PackageManager( 113): /system/app/Contacts.apk changed; collecting certs
D/PackageManager( 113): Scanning package com.android.contacts
D/PackageManager( 113): Shared UserID android.uid.shared (uid=10022): packages=[PackageSetting{4605c8e0 com.android.providers.applications/10022}, PackageSetting{4605c5c8 com.android.providers.contacts/10022}, PackageSetting{46057a90 com.android.contacts/10022}, PackageSetting{4605bf48 com.android.globalsearch/10022}, PackageSetting{4605b5d0com.android.providers.userdictionary/10022}]
E/PackageManager( 113): Package com.android.contacts signatures do not match the previously installed version; ignoring!