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).