Hola Ariel com estas,
Para poderte dar un buen apoyo, necesitamos de algunos datos, ejemplo:
1 - De que manera haz dado de baja dicho server ?
2 - Postea el mensaje.
3 - Desde ADSI, que patch verificastes ?
4 - Desde el nuevo server a joinear, modifica el DNS e intenta nuevamente
5 - Modifica el SID
6 - Remueve todos los records en DNS.
Espero sea de ayuda para avanzar.