Se ha producido un problema de comunicación con los servidores de Google, inténtalo más tarde - Galaxy s3

Me ha aparecido el temido error "Se ha producido un problema de comunicación con los servidores de Google, inténtalo de nuevo más tarde". Todo empezó con notificaciones que indicaban que mi cuenta no podía sincronizarse con ninguna de mis aplicaciones. He visto muchos mensajes con posibles soluciones ...

1. He eliminado la cuenta, he intentado volver a añadirla y he recibido el mensaje anterior. Intenté añadir otras cuentas... lo mismo.
2. Verificado 2-factor auth no está habilitado
3. Borrado de caché y datos de todas las aplicaciones de tipo Google en el teléfono, desinstalado todas las actualizaciones de las aplicaciones ....restarted
4. Verificado que el ajuste de la fecha/hora y la zona horaria son automáticos y parecen correctos.
5. La red y wifi están bien ... puede navegar a los sitios de Google
6. Teléfono no rooteado. Sin embargo verificado el archivo hosts es legítimo
7. No estoy dispuesto a hacer un restablecimiento de fábrica, ya que otros mensajes sugieren que esto no siempre se soluciona el problema y que sólo me llevaría a tirar probablemente mi teléfono. Consecuencias no deseadas.
8. Intentado desbloquear Captcha en la cuenta de Google

Esto ocurre independientemente de la cuenta de Google que intente añadir, lo que me hace pensar que no está relacionado con la cuenta, sino con el teléfono.

Me estoy volviendo loco... está claro que hay un problema grave y no consigo resolverlo. ¿Alguien tiene alguna sugerencia.

Gracias