If the "clear data" in the sync app idea does not work (it did not for me), it may be the issue where all your contacts are labeled "phone" or "sim" and have not been associated with your Google account. Use the technique in this video:
Samsung Galaxy S3 : How To Backup/Restore Contacts - YouTube
Export all your contacts to something, whether it's to "USB" (which actually just saves to your phone's My Files (Apps > My Files > /storage sdcard0 and the file is there) or to an added SD card. Like in the video: Contacts app, menu button, export, etc.
Then delete all your contacts in the Contacts app. Yeah, I know, you're nervous right now. Rightfully so, I was too. But remember, you just exported them all to a file that's sitting there on your phone, so you haven't, and won't, lost/lose the contacts.
After your Contacts app is empty, do menu button, import from the same place you exported to,
"SAVE CONTACT TO" GOOGLE (is it painfully obvious how important this aspect is?), and go find that file. Then all your contacts should have a little blue g next to them.
At this point, the sync has likely already started and if you're viewing Google contacts (google.com/contacts) on your laptop you can watch it sync real time. If it's not auto-syncing, you can go to the Contacts app, menu button, Accounts, choose the Google one, and sync now.
If this doesn't work, sorry I have nothing more. It worked for me and I'm stopping here
