A mí me paso eso una vez cuando tenía la original 2.1 y lo solucioné así:
Entras en Ajustes, Aplicaciones, Administrar aplicaciones, Información de los contactos y dentro ejecutas borrar datos. Al volver a sincronización ya te debería funcionar.
Esto no te valdrá en tu caso porque se te borrarían los contactos google del teléfono. Yo tenía los contactos previamente como google y los mismos en gmail y me funcionó; tendrás que buscar otra solución...