Hola a mi me paso lo mismo, la solucion fue eliminar del movil la cuenta de google y todas las apks relacionadas con google. Reinicias en recovery y wipe cache y dalvik-art cache, reinicio normal.
Despues te descargas este zip
https://drive.google.com/open?id=1bC...yvIlHPQPaEFEMC, lo descomprimes en el pc y pasas todas las apks a la memoria del telefono.
Despues instalas una por una todas las apks en el orden del parentesis ( ), excepto el play-store, reinicas en recovery otra vez wipe cache y dalvik-art cache, reinicio normal.
Entonces instalas el play-store, entras en el, te logueas, se actualizan todo lo relacionado con las cuentas de google y a funcionar normalmente.
Saludos y espero que te funcione como a mi...