a ver... vamos por partes... Toda cuenta en Active directori (cuenta usuario, maquina o grupo) tiene un SID unico, este SID es una rista de numeros que identifica el objeto dentro del AD(AD= Active Directory) en dicha cadena de numeros hay una parte que identifica el dominio, si has despromocionado el servidor de dominio para crear el dominio de nuevo las maquinas que ya tenias metidas las tendras que volver a meter (para ello primero las vuelves a pasar a grupo de trabajo y luego las vuelves a entrar en el dominio nuevo) es es porque al crear el dominio de nuevo, todo y llamarse igual la parte de SID que identifica el dominio a cambiado.
Cuando tengas tiempo pasate por el sigüiente link, es de un espacio web mio donde tengo un pequeño manual de 2003, leetelo por encima, con eso creo que entenderas un poco mas como funciona el windows 2003 y los servicios que puede ofrecer, entre ellos el DNS y el AD
http://personales.ya.com/spa_hyperion/w2k3.zip