Hubo un problema al comunicarse con los servidores de Google, vuelva a intentarlo más tarde - Galaxy s3

Recibí el temido error "Hubo un problema al comunicarse con los servidores de Google, inténtelo de nuevo más tarde". Todo esto comenzó con notificaciones que indicaban que mi cuenta no podía sincronizarse con ninguna de mis aplicaciones. He visto muchas publicaciones con posibles soluciones...

1. Eliminé la cuenta, luego intenté volver a agregarla y obtuve el mensaje anterior. Intenté agregar otras cuentas... lo mismo.
2. La autenticación de 2 factores verificada no está habilitada
3. Se borraron la memoria caché y los datos de todas las aplicaciones de tipo Google en el teléfono, se desinstalaron todas las actualizaciones de las aplicaciones... se reiniciaron.
4. Verificado que la configuración de fecha/hora y la configuración de zona horaria son automáticas y parecen correctas
5. La red y el wifi están bien... puede navegar a los sitios de Google
6. Teléfono no rooteado. Sin embargo, verificó que el archivo de hosts es legítimo
7. No estoy dispuesto a hacer un restablecimiento de fábrica todavía, ya que otras publicaciones sugieren que esto no siempre soluciona el problema y eso solo me llevaría a tirar mi teléfono. Consecuencias no deseadas.
8. Intenté desbloquear Captcha en la cuenta de Google

Esto sucede sin importar qué cuenta de Google intente agregar, lo que me hace pensar que no está relacionado con la cuenta sino algo en el teléfono.

Estoy al límite de mis conocimientos ahora ... claramente hay un problema grave aquí y no puedo identificarlo. ¿Alguien tiene alguna sugerencia?

Gracias