Quando você tiver problemas com o Active Directory, verifique primeiro o DNS. Se tudo estiver OK, você deve se perguntar "What DNS issue did I miss?"
e então verificar o DNS novamente.
Aposto meu bonnet que você não está usando o controlador de domínio como o servidor DNS nos clientes com problemas. Defina o IP para os servidores DNS nos clientes Windows que tenham o problema de usar os controladores de domínio e os controladores de domínio sozinhos para o DNS.