Default Rooted SGS4 - Play Store does not connect (either Server Error or No Connection)

Now, you guys probably have seen a few of these threads from the past but hear me out:
I rooted my Verizon Galaxy S4 today with this method, and it successfully rooted my phone. But when I tried launching Google Play/related apps or Gmail, and I'm on my wifi (I don't know if this is just mine, or if it will not work over any wifi, cannot test yet), I either get Server Error or No Connection. Also, notifications say that my connection is unstable despite the fact that it wasn't before root. I narrowed down the Server Error to Adblock Plus, but I get No Connection on my wifi with it disabled. It worked fine before root even with Adblock Plus, but now it's being weird after. I've tried MarketEnabler, clearing the Google Servives Framework and Google Play data/cache, unlinking my Google account, reinstalling Google Play, etc. But all to no avail. Reflashing gapps is not an option because I do not have a custom recovery because of a locked bootloader. So what else could I possibly do to fix the issue? I don't want to have to download all my apps with data because that could rack up huge charges for big apps. I also do not want to have to unroot or restore factory defaults. I haven't touched any apps (besides freezing TouchWiz Home, because I use a different launcher, and Knox Notification Manager in Ti, which shouldn't even affect Google Play or Gmail). So, yeah. That's my issue.