Ya está arreglado!
Eliminé la cuenta de google, borré los datos de Play Store y de Marco de Servicios Google como había hecho anteriormente y reinicié el móvil.
Después volví a crear la cuenta de google, esperé a que se sincronizaran los contactos, emails, etc. y ya funciona todo perfecto.
Gracias!
