If you Froze (or Disabled; an ICS and above feature built in, no rooting needed) your rooted device's AUTHENTICATORS - Doesnt matter which - AND you have an equivalent email using that Authority as one of your contacts, then you either need to Delete that contact OR turn on the needed Authenticator.
So. ifyou have a hot mail, live, or msn contact, you will need those to Authenticate AND you WILL need to either freeze or uninstall hotmail (if Outlook is installed). In all other cases, say if you have say a Yahoo contact in your contacts, Yahoo Authenticator must be available. This is a general Authenticator bug that should get fixed OTA via Google Play Services update ONCE ALL AUTHENTICATORS MIGRATE TO OpenID v 2.0 by March 23rd 2015.
If you UNINSTALLED any Authenticator, the ONLY way to get it back is to Factory Reset. Period. DO NOT TRUST any available source for a system apk.