Problema con usuarios nuevos

Hola a todos, de antemano gracias por su ayuda.

Mi problema es el siguiente, tendo un Server 2008 como controlador de
dominio, con AD funcionando, he creado unos usuarios nuevos y cuando me
intento logear desde los teminales con estos usuarios me sale un mensaje
que
dice que el dominio xxxx no esta disponible, sin embargo, si me logeo con
alguno de los usuarios anteriores, me funciona perfectamente.

¿alguien podría decirme por qué podría estár ocurriendo esto?

Un saludo

P.D. Necesito solucionalo lo antes posible, mi situación es desesperada