A rede funciona e você está relatando isso como acontecendo em vários computadores. Eu diria que você precisa olhar para:
- DNS: tente fazer nslookups nos controladores de domínio quando ocorrer uma falha. Tente consultar o nome do domínio e veja se você está recebendo de volta uma lista válida de CDs.
- Aplicativos que você executa nos PCs que podem ser muito inteligentes para seu próprio bem. Especialmente firewalls, av, etc.
- Regras de firewall de rede. Você está tentando bloquear portas > 1024 entre os PCs e DCs? O Windows não gosta de restrições de intervalo de portas.