Hay varios problemas relacionados a google play store y play services.
Lo basico es eliminar los datos y cache de las apps, forzar el cierre y volver a abrirlas.
Otra opcion un poco mas drastica sería desinstalar las actualizaciones de play store y play services y volver a instalar.
Antes que nada verifica que la fecha y hora de tu dispositivo esten bien seteadas.
Abres play store, cuand osale el error, presionas menu y la minimizas, ahi vas a ajustes, aplicaciones y a administrar aplicaicones.
Aqui vas a la pestaña (arriba) "En ejecucion" o a "Todo" y buscas Play Store, entras a los detalles dando un tap sobre el y ahi tienes la opcion de eliminar caché y eliminar datos ademas del forzar cierre. Si no la encuentras ahi puedes buscar el servicio dando un tap en el boton (arriba a la derecha) que dice "mostrar procesos en cache" y la matas, y borras todos los datos y cache, luego la finalizas con el cierre forzado.
Haces los mismos pasos para "marco de servicios de google" o "play services".
Luego reinicia el dispositivo.
Hay una opcion antes de reiniciar el dispositivo que es: previo a todo el proceso mencionado instala ccleaner por fuera del market, descargando la app y limpia todo la basura que hay en el telefono. Ya ese es otro tema mas complicado el de instalar por fuera, descargas el apk, en la pestaña de seguridad dentro de ajustes vas a habilitar "fuentes desconocidas".
Suerte con eso, y cualquier cosa estoy por aqui cada tanto.