borrar datos de google service en ajustes del sistema-->aplicaciones-->todas->servicios de google play.
borrar datos de la misma manera de Gplay.
Desinstalar actualizaciones de ambos (en el mismo sitio si se a actualizado te sale la opción).
Yo esta no la he encontrado pero algunos afirman que cuando da el error vas a ajustes del sistema-->Aplicaciones-->en ejecución y al final de la lista sale una opción de descargas se borran datos y se arregla el problema (como dije esto yo nunca lo he visto).
Si sigue saliendo el error prueba estas opciones.