Verifique se o seu DC está respondendo na porta 53 (porta padrão do DC baseado em Windows), se não for este o problema.
Eu configurei meu controlador de domínio primário no Ubuntu 11.10.
Para ter certeza de que funcionou, usei um cliente do Windows 7 no meu laptop de amigo e consegui fazer login com êxito como usuário do meu domínio.
Mas quando tento testar outro laptop, ele falhou com essa notificação.
An Active Directory Domain Controller (AD DC) for the domain"MYDOMAIN" could not be contacted. Ensure that the domain name is typed correctly. if the name is correct.click Details for trouble shooting information.
O que há de errado? Configurei o cliente com falha igual ao cliente que foi bem-sucedido e digitei o domínio corretamente.