En estos dias justamente me estaba pasando lo mismo. La solución fue limpiar la data de los contactos en el celular (borrando TODOS los contactos) y volver a sincronizar con Gmail. Eso sí, había respaldado todos mis contactos en el Gmail previamente.
Si tienes todos tus contactos en el celular, los puedes respaldar yendo a la lista de contactos -> Menu -> Importar/Exportar -> Exportar a tarjeta SD.
Con el archivo VCF del respaldo, lo puedes importar a tu cuenta de Gmail.
Para limpiar la data de los contactos, te vas a Menu -> Configuraciones -> Aplicaciones -> Administrar aplicaciones -> Almacén de Contactos -> Borrar data (Asegurate de que hayas respaldado todos tus contactos, ya que en este paso se borraran completamente del telefono)
Luego le das a sincronizar (preferiblemente con Wifi) para que vuelvas a recuperar todos los contactos.
El idioma de mi Wildfire vino en Inglés solamente, por lo que los nombres de las opciones es probable que varíen.
Saludos