Olá!
Detalhe o tipo de Rede em que seus clientes trabalham.
E como disse nosso amigo Lucas Simões, verifique o DNS.
Faça uma análise minuciosa começando do Servidor, se não fora executado alguma modificação nesta Rede para ter acontecido isto. Desconecte as máquinas e vá testando a ligar máquina por máquina, quem sabe alguma passou por alguma alteração. Você conseguirá,
o erro está entre o servidor até a última máquina.
Espero ter lhe ajudado
MS INFORMATICA - Projeto Marinner