I am having the same issue with Lumia 520. It will sync Calendar and Mail, but when I check Contacts, the sync fails with the above mentioned error... Damn you MS, or Google, whoever's fault it is!
Anyway, I tried with ActiveSync solution, the Contacts do sync that way, but not all of them and not every field. For example, any contact that has two or more phone numbers will sync only the first one. This is becoming really frustrating! I will now try to "sanitize" my contacts and see if it will help.
One question, though: does ActiveSync work both ways? If I change/delete/add contact to my WP, will the change show up in Google?