Domain Controller not auto enrolling Kerberos Certificate from new 2016 CA

Solution 1:

After researching this out and trying multiple CA certutil commands among other things I'll skip straight to the actual answer that worked for me:

Most of the time something like "RPC server is unavailable" can be attributed to network connectivity issues or firewall rules.

However, in my case the DCs having issues weren't running the Windows Firewall. BUT it turns out that was the very issue. Someone had decided instead of turning off the firewall (not best practice btw, but I digress) in the Network and Sharing Center, they instead Disabled the Windows Firewall service itself.

This is actually a bad idea as discussed here: How can I back up my recommendation to NOT disable the Windows Firewall service?

Answer:

1. On the problematic DC not getting the cert start the Windows Firewall service and set it to Automatic startup.
2. If required in your environment (likely since the service was stopped by someone), turn off the Windows Firewall in Control Panel, System and Security, Windows Firewall for the Domain network, etc. as required.
3. Verify that the secondary DNS server for that DC is pointed to itself via loopback address. In my case I had a few of these that weren't and their primary wasn't accessible over the WAN at the moment.
4. run certutil -pulse on the problematic DC
5. Check the application event log again (should show enrollment ok)