Verifique se as máquinas remotas podem realmente efetuar login no domínio. Tente reiniciar um deles e faça login como usuário do domínio. É provável que você não consiga efetuar login e receber o erro "relação de confiança". Se for esse o caso, faça login como uma conta de administrador local e reingresse no domínio deixando o domínio, reinicie e junte-se ao domínio novamente.