Ditto! Here is what worked for me. First, close your contacts. Then open your web browser on your mobile device. Navigate to
https://accounts.google.com/Login and re-login (re-connect to the server). Then try to sync your contacts. It worked for me.
Somehow I had lost contact with the server that supports GMAIL and contacts.