I had this problem for months and found an answer on another thread in a google forum that worked for me. It seems to be a well-known problem with android/gmail sync.
Back up your contacts first just in case. I exported mine to sdcard
Go to settings/applications/manage/all/contacts storage and clear data.
Then sync and all should be OK. Mine was anyway - ymmv. It seems the "contacts storage" app is the one that actually manages the database(s) and if you have a corrupt database on the phone nothing will fix it except clearing the database. A factory reset will do this obviously, but is a bit drastic.