I've been having a problem with my Android phone for a few weeks. I kept getting a "No connection" error when opening Play Store even though my Internet was working perfectly fine. On top of that I kept getting the dreaded "com.google.process.gapps has unexpectedly stopped working" error a lot randomly during usage. I've googled and tried everything (except a factory reset). Nothing helped. But then I tried restoring a few Google related apps from my last backup this summer (using Titanium Backup) and after a reboot, it started working again. :D
I also lost all my contacts this summer, but yet again a 2-month-old backup saved my ass. Remember to keep backing up your stuff. xD
Did you try clearing Google Apps local saved data, then rebooting into the recovery menu and clearing cache/dalvik cache? Also google backs everything up for me, other than app data, but it keeps my contacts and list of downloaded apps. After a new install and I sign in, it'll start downloading the apps I had previously installed.
I tried all of that like 5 times. xD
I disabled syncing, because I don't trust Google. I don't want my phone contacts to get mixed up with the shitloads of email contacts I have since there was a time where GMail would add anybody to the contact list if they sent you an email. They still kinda do.
I've been having that play store problem too... ever since I did that kitkat upgrade...
It's not just Kitkat. Play Services updates itself in the background without you confirming anything. That's what happened to me. Google messed up. :/