Fixing KDC Authentication Problems when upgrading your domain and forest functional level from 2003 to 2008 R2

We recently upgraded our Domain and Forest Functional Level from 2003 to 2008 R2, after a day or so I started having problems connecting to a number of 2008 R2 Hyper-V Virtual Machines. When attempting to connect I would receive the following error:
An Authentication Error Has Occurred. The Encryption Type Requested Is not supported by the KDC
At around the same time we also had one of our Exchange 2010 Transport Servers stop servicing clients, when I attempted to open the Exchange management console on the local server console ended with a HTTP server error status 500 and “Kerberos” authentication failed. So I decided to take a look through the event viewer to see what was up.

As part of Exchange there is an Active Directory Topology Service which will scan your environment for Active Directory Servers every 15 minutes or so, all of the exchange services rely on this service (if you ever have to restart all exchange services, simply restart the AD Topology Service). In the application event log I noticed the following error message:
Process MSEXCHANGEADTOPOLOGYSERVICE.EXE (PID=xxxx). Topology discovery failed, error 0×80040952 (LDAP_LOCAL_ERROR (Client-side internal error or bad LDAP message))….
There were also issues with the Exchange STORE service with the following two events:
Process STORE.EXE (PID=xxxx). All Global Catalog Servers in forest DC=xxx,DC=xx,DC=xx are not responding.
Process STORE.EXE (PID=xxxx). All Domain Controller Servers in use are not responding

The rather simple resolution to all this trouble is simply to restart the KERBEROS DISTRIBUTION KEY or KDC service on all Domain controllers. While simply restarting the Service will solve the problem, you’re probably better off just doing a proper restart after upgrading your functional levels, only from 2003 to 2008 / 2008 R2.