Info 2 [solution] "There was a problem communicating with google servers."

I recently removed knox and rooted my phone following the guide. Worked great... I got into my phone with CM10, except for a constant "There was a problem communicating with google servers. Try again later." error message. I thought it was a bad wipe, so I rewiped and reflashed the ROM. No joy. I did a full factory reset from the menu. No joy.

Searching on Google and XDA yielded a lot of messages about the Google servers going down a few years ago. Obviously this wasn't the case. Finally, I found something that worked:
  • Disabled 2-step Authentication (mostly to make it easier on myself)
  • Removed the account
  • Cleared the data on the "Google Account Manager"
  • Readded said account

This worked for me. I'm on CM10.2.1-dspr (stable).