I remember having gone through the same problem years back (on a froyo device). Not sure what caused it, but I fixed it as follows:
- Exporting ALL your google contacts to a file (make sure everything is in there)
- Remove all contacts from google
- Remove all contacts from phone
- Import the contacts from the file (exported in (1)) to the PHONE
- Sync the contacts
- Verify whether the sync worked
After doing this two way sync worked perfectly for me. I can not guarantee that this will work for you, but it may be worth a try. Also, make very sure that the export in (1) is complete (check the contents of the file) - also, export to various file formats for safety.
Unfortunately, the changes you made on the phone will have been overwritten and I do not know of a way to revert that. In the future, if the problem persists, you can disable the sync and do it manually using files - it sucks, but at least you won't lose information.