Mouseglider's method does allow me to sync, but any contacts that I added to my account using my phone were wiped out because they were never synced to Google's servers.
I noticed something that else that may be causing the issue for others as it was for me. I was using Go Contacts EX app as my contacts manager app. If I use the stock contacts app to add a contact, it syncs to Google just fine. As soon as I add one using Go Contacts EX, following sync attempts fail.
Are you rooted?
If so, use rootexplorer to navigate to /data/data. Find the directory labeled "com.android.providers.settings" and delete it. Reboot, and your Google contacts should now sync!
Try this:
First, press menu and go to "settings" - click on "Accounts & snyc" - uncheck "background sync" - now use your back key to get back to the screen where you saw "Accounts & snyc" and then click on "Applications"
Locate "Contacts Storage" - if you can't find "Contacts Storage", click menu again and select filter, then select all - open the "Contact Storage" and click "clear data" of "Contacts Storage"
Get back to the first step above and recheck "background snyc" - it will start to snyc and take anywhere from 2 minutes to 15 minutes
If you have problems with "calendar" and "gmail" do the same steps above to for "Calendar Storage" and "Gmail Storage"
Try this:
First, press menu and go to "settings" - click on "Accounts & snyc" - uncheck "background sync" - now use your back key to get back to the screen where you saw "Accounts & snyc" and then click on "Applications"
Locate "Contacts Storage" - if you can't find "Contacts Storage", click menu again and select filter, then select all - open the "Contact Storage" and click "clear data" of "Contacts Storage"
Get back to the first step above and recheck "background snyc" - it will start to snyc and take anywhere from 2 minutes to 15 minutes
If you have problems with "calendar" and "gmail" do the same steps above to for "Calendar Storage" and "Gmail Storage"