Change certificate auto enrollment settings from long gone CA to new CA

We started getting event ID 13 from a our domain controllers:

Certificate enrollment for Local system failed to enroll for a DomainController certificate with request ID N/A from OLDSERVER.domain.local\oldserver (The RPC server is unavailable. 0x800706ba (WIN32: 1722)).

OLDSERVER was a 2003 domain controller and certificate services server that was removed from the domain at least a couple of years ago. All our current DC's are 2008 R2 and the functional level was raised to that as well.

Where can I begin to change which CA is registered for this auto enrollment?

First off, remove the old CA from being registered in AD - use the Enterprise PKI snap-in to remove every trace of the old CA from the AD Containers, see here.

Next, make sure you have an enterprise CA that's configured to issue that certificate template (or move the autoenroll setting to a more modern template for your DCs like Kerberos Authentication).

Then, force a re-enroll on the certificate template, so your DCs will enroll a fresh cert instead of trying to renew against a long-dead CA. Make sure everything connecting to the DCs trusts the new CA before you do this.