A mi también me pasaba lo mismo y acabo de solucionarlo. Yo lo que he hecho es reestablecer los datos de fabrica del telefono y despues (teniendo el telefono rooteado) accedes al root explorer (o bien al ES File explorer) y te vas a la carpeta ETC y dentro hay un archivo llamado hosts lo abres con el editor de texto y borras la linea "XX.XXX.XX.XXX
android.clients.google.com.". (las X son numeros que pueden variar).
(Para poder editar y borrar la linea recuerda que tienes que tener activado en herramientas-explorador root-mount R/W y señalar todas las opciones RW si no no te deja borrar la linea).
Espero que te sirva de ayuda, un saludo