Solution does not require factory resets wiping data/downloads ect.
All you need is a rooted phone and about a minute of your time.
So go to root browser and find a folder ect in that folder you will find a file called hosts open it up and edit second line of the text.It should look like this (2nd line).
74.125.93.113 android.clients.google.com mtalk.google.com
after that save and reboot your tablet/phone.From what I know every time you restart your router it will go to grey again so just edit that file again if it happens.