Assumo que o servidor em questão não é um controlador de domínio. Nesse caso, você verificou suas configurações de DNS?
Eles devem ser configurados para usar o mesmo servidor DNS que seu AD está usando.
Você pode realizar um nslookup no seu nome de domínio do servidor?
Por exemplo (supondo que seu nome de domínio DNS seja example.local)
h:\> nslookup example.local
Server dc1.example.local
Addresss: 1.2.3.4
Name: example.local
Addresses: 1.2.3.4, 1.2.3.5, 1.2.3.6
Vale a pena verificar, como em minha experiência, esse tipo de erro geralmente está na configuração do DNS estar errado em algum lugar ao longo da linha.