La solución es: (la que me sirvió a mi)
Configuración--> Aplicaciones--> Uso de memoria
En Uso de memoria señalas la opción TODAS
Buscas "google play Store", entras y pulsas borrar datos
Luego buscas "MARCO DE SERVICIOS DE GOOGLE", entras y pulsas borrar datos
Una vez esto, reinicias el terminal