I have tried all suggestions in the answer and everything the asker did specified on this question without any luck. I reflashed GApps and CyanogenMod at least 13 times, as I have lost count. The only things that seem to be malfunctioning is Google Play. Although sync says it's having "errors" but it is syncing so I'm not sure what is going on there...
What is working:
- Apps with the "login with Google" that uses the Google+ API
What's not working:
- Google Play
What's half working:
- Sync, it says it's having errors but it is syncing
- CyanogenMod 10.1.3
- Android 4.2.2
- GApps for CyanogenMod 10.1
- Samsung Galaxy Tab 2 10.1 (GT-P5113)
I have the Xposed framework installed, but it's never caused problems before so I wouldn't think it would be a problem now. The time is as it should be, so it's not the problem. Cleared the cache and data on Google Play 37 times.
P.S.: When I say "reflashed", I mean I wipe /system /cache and the dalvik cache and install GApps, CM 10.1.3 from zip in recovery.