Eu não vi isso antes, mas meus pensamentos iniciais seriam que, como os tickets do Kerberos são baseados em tempo, o atraso entre dcpromo
e reinicialização poderia ter causado o problema.
Você tentou des-promover o novo servidor e fazer um novo dcpromo e reiniciar?