Yo le he hecho un hardreset y lo he borrado todo, (demasiadas aplicaciones que me drenaban la bateria) y al instalar me ha dado el mismo error, tan solo he instalado los servicios de google play, antes de dejar que se actualizase cualquier programa, y 0 fallos.
https://play.google.com/store/apps/d...roid.gms&hl=es
Si no tienes claro las Gapps que tienes que instalar, descargate Gapps Manager, Tiene practicamente todas.
https://play.google.com/store/apps/d...s.gappsmanager te vendrán todas las disponibles, tan solo debes de seleccionar tu versión.
Si ves que te sigue dando error al acceder a la playstore, haz un borrado de la cache, y datos, yo tengo inavilitadas las conexiones automáticas de la aplicación, por que consume demasiados datos en 2ºplano, solo se conecta por wifi, aveces me da error y tengo que matar el progreso, para reiniciarlo y poder entrar en la tienda.