Um computador pode ter vários "nomes" na rede. Existe um nome que o computador possui. Há um nome no sistema DNS local preenchido por meio de descoberta ou atualização automática ou propagação de DHCP. Pode haver registros "A" especificamente atribuídos no DNS conectado ao endereço IP. E há o nome da conta do computador no Windows Active Directory.
Assumindo um domínio padrão do Windows, o que você deve ter feito é mudar o computador para estar em um grupo de trabalho, que exclua a conta de domínio do computador com o nome antigo e adicione o computador ao domínio com o novo nome. Apenas alterar o nome resulta no tipo de comportamento inconsistente que você descreve, porque os nomes não são sincronizados corretamente.
Uma solução alternativa ... remova os computadores do domínio, exclua manualmente quaisquer contas antigas perdidas do Active Directory, exclua manualmente qualquer nome de computador antigo perdido do DNS e coloque os computadores de volta no AD.