The following error occurred while attempting to connect to the specified Exchange Server
The attempt to connect to <mail server> using “Kerberos” authentication failed
…after changing the Domain Administrator password and trying to open Exchange 2010 Management Console. After much digging it turns out that some old credentials were stored in the Windows Credential Manager
So just fire up Credential Manager (search from Start Menu) and delete any Windows Credentials that pertain to your server
