Happened to me too. Backup everything in gmail to a csv, delete all contacts, then resync everything. Backup your contacts on you phone too, use an app called ExportContact. Take the csv and import to gmail. Worked for me!
The problem (for me) was verizon added my contacts to my phone and it messed things up.