Por lo visto no es un problema aislado. Buscando encontré en el foro del Galaxy Nexus el mismo problema, y con esta solución lo solventaban:
Eliminar la cuenta de google, borrar los datos de Play Store y de Marco de Servicios Google y reiniciar el móvil.
Después volver a crear la cuenta de google, esperar a que se sincronicen los contactos, emails, etc...
A ellos les funcionó, a mi desde luego que no. Tendré que restablecer el teléfono al final...