I'm slightly late to this topic (about 6 months late). However, I wanted to register my name here and offer my 'sage' (yeah I use that term sarcastically) advice.
I had this exact issue this evening after a power outage. My phone had died and I couldn't figure out what the heck was going on. I had partial internet connectivity, some things worked, but all Google services where DoA. I found out, my date had be reset to January 1 1970... needless to say after a slightly red faced moment, I reset the date and all's well that ends well. Immediately all my 'broken' services where made whole again.