We have a Windows 2008R2 DC where the KDC does not start on reboot. It can be manually started OK once the system is up. The service is set to automatic start, and the services/devices that KDC depends on all seem to be started before KDC attempts to start.
The only indication of a problem is two event ID 4311 events, both identical:
"Initialization failed because the driver device could not be created. Use the string "001A4BFE6F6A" to identify the interface for which initialization failed. It represents the MAC address of the failed interface or the Globally Unique Interface Identifier (GUID) if NetBT was unable to map from GUID to MAC address. If neither the MAC address nor the GUID were available, the string represents a cluster device name. "
The string referenced above is the MAC address of the one enabled NIC on the system. I can see events in the system log that indicate the NIC has been intialized. Microsoft PSS has been working on this for a while with no discernable results. I'm sure someone out there is better than MS PSS ;)