I had this problem and had to copy my contacts to my SD card (contact list-menu-import/export-export to sd-then choose which contacts list you want to export (either sim, phone, or google). Then once you have done this place the sd card in the pc or hook your phone up to the pc as disk drive and find the file on the sd card. Log in to your Google account on your pc in your contact list there should be an import option might be under a more actions tab. Import the file from your sd card.
Once I did this my contacts had no problem syncing to Google.