After updating to Mavericks (OS X 10.9) I’ve seen a few instances where “The server encountered an error verifying registration” errors appear when trying to open FaceTime after an upgrade. I think this comes down to the GUID/username entry for the Accounts not matching the AuthID in ~/Library/Preferences/com.apple.ids.service.com.apple.madrid.plist file. It seems as though the accounts that work have a consistent entry here and those that don’t have random or missing information. If some of the keys are filled in and the Status for each alias is 3 it doesn’t appear to try and connect again. The easiest and quickest way to fix this for me has been to delete the ~/Library/Preferences/com.apple.ids.service.com.apple.madrid.plist file with Messages closed. Also, the ServerHost key needs to be init.ess.apple.com. I’ve noticed that when the AuthID is inconsistent that the ServerHost is missing.