A thought popped into my head today. On all ROMs I tried to use I always installed Freedom for free in-app purchases. I also installed it on this phone, but only on the custom ROM. I have been using the stock ROM perfectly. I went into Freedom and stopped it properly by pulling up the settings menu and hitting Stop. Then I uninstalled it. Straight away I went to Play Store and I had access again. Same for Gmail.
So my assumption is that Freedom caused the issue. It took a while because I havn't used Freedom in a month or so and the issue just started happening. However, once I removed it properly everything worked fine. When I wiped my old phone I never removed Freedom so i'm not sure if that messed something up that a basic factory reset couldn't fix. The other reason this is an assumption is because I was not able to test this on my old phone. But I figured I would let you guys know. If you have issues with Google services and have Freedom installed, try uninstalling it. But first, MAKE SURE YOU STOP IT FROM THE IN APP SETTINGS!