Há uma infinidade de fatores.
Apenas fora do topo da minha cabeça. . .
Qual erro o NSlookup retorna? Está usando o NetBIOS? Ou está apenas falhando após consultar o servidor DNS?
Quais são as configurações de IP em cada computador?
Quando você se conecta de B a A usando RDP, presumo que esteja usando as credenciais "domínio \ usuário" ou "usuário @ domínio", você já tentou um rdp de A para B usando o endereço IP?
Quando você tracerta, onde está falhando? Você está usando o endereço IP ou um nome resolvido?
Em resumo, liste os erros que você recebe. Apenas dizendo que eles não se conectam pode significar qualquer coisa. Pelo que sabemos, um hamster caiu do volante.