Google Play Store no longer allowing installs/updates

I'd suggest checking other networks too before the factory reset (to make sure it's not the network blocking the servers somehow). Also, try with another account (if it's your account in particular, then you know it's a Google issue).