Default Can't Establish Reliable Connection

Hello guys,

So I'm on the Verizon network and since the OTA update for KitKat has been released I've been having a problem.
Since I updated to 4.4.2 I can't seem to log into anything Google related without the error..

"Can't establish a reliable connection to the server."

I've contacted Google, Verizon & Samsung and they can't do nothing but give me troubleshooting tips.
I've already factory reset my phone 3 times, and the error still persists.

Since my phone IS NOT rooted, I can't edit the hosts file.
Is there anything that can be done in the mean time until root access has been found?
Phone - Samsung Galaxy S4 - VRUFNC5 4.4.2
ROM -(Stock)
Kernel - (Stock)
Root - N/A