If you go to Settings/Applications/Manage Applications/ then choose the All tab. Scroll down to Contacts open it and clear the data cache. Now do the same again but this time open Contact Storage and also clear the data cache. This issue is related to an Android bug and affects many devices. It's related to apps that use the sync function.