El problema es accesar a esa carpeta ntds.
Los usuarios se encuentran en la base de datos?
Si es asi podrias hacer esto desde la consola:
http://support.microsoft.com/kb/816120/es
De cuantos usuarios estamos hablando... si son de 60 a 100 hacerlo a mano es los mas seguro y factible... el problema seria mas de 500 usuarios ahi si tendrias que recuperarlos desde un respaldo de AD que tengas...
Si levantas el dominio de nuevo aunque se llame igual tienes que meter los equipos al dominio de nuevo para crear el registro en el AD de nuevo
suerte...