dcpromo prerequisites for Active Directory preparation failed

Question

Cannot promote a new Server 2012 R2 server to domain controller on an existing domain. The prerequisites check fails.

Verification of prerequisites for Active Directory preparation failed. 
Unable to verify whether schema master has completed a replication cycle after last reboot.
Exception: Unavailable Critical Extension. Server extended error: 8366.
Server extended message: 000020AE: SvcErr: DSID-03210384, problem 5010
(UNAVAIL_EXTENSION), data 8610
.
Adprep failed to verify whether schema master has completed a replication
cycle after last reboot.
[Status/Consequence]
The schema is not upgraded.
[User Action]
Check the log file ADPrep.log in the
C:\Windows\debug\adprep\logs\20160222090334-test directory for possible cause of failure.

Current domain has a Server 2008 R2 domain controller, with Domain Functional Level set to Server 2008 R2.

When trying to retrieve the Forest Functional Level the error "A referral was returned from the server" is encountered.

Solution

Issue due to replication failures with old domain controllers that no longer exist.

Needed to remove orphaned domain controllers and domains. I used the following guides:

https://support.microsoft.com/en-us/kb/251307

https://www.petri.com/delete_failed_dcs_from_ad

https://support.microsoft.com/en-us/kb/230306

Comments

[Drifter104]

How many DCs are present in sites and services? Are there any failed ones still there

[Ash]

Thanks for pointing me in the right direction. There were old domain controllers and domains which I have just removed using metadata cleanup.

[Lex]

What that the server holding the schema master? Make sure all the FSMO roles holders are valid (run "Netdom query fsmo" to validate)

[Ash]

Yep all FMSO roles are on the required DC.

[Michael Blackburn]

the Petri.com link is super-helpful, thanks!