dentro de contactos / ajustes , no tienes la opción "borrar duplicados" ?
lo suyo seria hacer una copia de seguridad de los contactos desde gmail en el pc ..entrar en gmail / contactos / mas .. y hacer una expor a un archivo .csv
una vez hecha , eliminar todos los contactos de gmail (en el pc) ..dejarlo todo limpio .
en el movil , intentar hacer lo mismo ..borrar todos los contactos
una vez limpios los contactos de los dos sitios , abrir gmail en el pc y hacer lo mismo que antes pero importando desde el archivo .csv guardado antes .
sincronizar el movil y esperar que hay suerte