Clark that's not cool. Are you sure that you have network permission enabled for both Play Service and Play Store? Another thing you could try, just to be sure, is to disable network permission for both apps, reboot, reenable, reboot again and check if it works.