I would update the Installation instructions as follows :
adb shell rm -r /system/app/Contacts.*
adb shell rm -r /data/dalvik-cache/system@app@Contacts.firstname.lastname@example.org
adb shell rm -r /data/data/com.android.contacts/shared_prefs
adb shell rm -r /data/data/com.android.providers.contacts/shared_prefs
adb push Contacts.apk /system/app/Contacts.apk
It could be that some commands will return an error because the directory or file is not found (depending on the previous installation), just ignore those.
Edit : People with apps2sd and dalvik-cache on SD will have to update the above commands to fit their installation ofcourse...
NOTICE: I do not respond to tech support questions through PM.