Following this week's releases of CyanogenMod, there's finally CM 12 and CM 12.1 releases for the Samsung S4 Mini. Therefore, I upgraded from the latest 11 release to 12.1.
However, after installing, I was unable to access the Play Store, getting "No Connection" and a "Retry" button opening it up. Following instructions from various places, I tried changing the date and resetting it, and then tried removing my Google account from the device. This is where I am now stuck.
Opening the Play Store now, it sits "Checking info...", occasionally telling me "Unfortunately, Google Play services has stopped" (it's been prompting me to upgrade Google Play services ever since I installed CM 12.1, as one would expect, but I've been unable to upgrade it due to lack of access to the Play Store) a variable number of times while doing so. Eventually, I reach a screen telling me:
Can't establish a reliable connection to the server.
This could be a temporary problem or your Android device may not be provisioned for data services. If it continues, call Customer Care.
However, internet access works fine in Chrome and in all non-Google apps. I can load play.google.com almost instantly in Chrome: there's no internet connectivity issue here.
Trying to add my Google Account from settings leads to the same "Checking info..." sequence of screens.
How can I re-add my Google account and regain access to the Play Store?