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