Somewhere in the dark and wet Northwest.
Are you synching facebook contacts?
That could be an issue. I've seen that in the past.
Found these two, thought you may have already tried them.
find Google Services Framework and clear the cache (if any) and clear data. Reboot, and you should be good to go.
settings ->application manger -> all-> and clear data on contact and contact storage in app manager. But... Your data for contacts will be wiped away. So remember to BACKUP!