Você tem uma rede baseada em domínio? Nesse caso, é possível que o novo servidor tenha sido instalado como uma estação de trabalho não associada ao domínio, o que causaria esse problema exato. Juntar a máquina ao domínio pode ser a resolução, mas eu não faria isso sem falar com sua equipe de TI ou com o consultor que instalou o servidor para você.
Se o servidor em questão for o Controlador de Domínio da sua rede, talvez seja possível que alguns ou todos os Relacionamentos de Confiança tenham sido quebrados entre as estações de trabalho e o domínio, o que também causaria o problema descrito por você.
Você deve examinar os logs de eventos das estações de trabalho e dos servidores para ver se há algum problema relacionado ao acima nos logs.