Soa como resolução de DNS. Se estiver na mesma sub-rede, não poderá ser o firewall.
Você pode fazer o ping dessa máquina tanto pelo nome do host quanto pelo nome de domínio totalmente qualificado em ambas as direções?
Bem, se eles estiverem usando o mesmo servidor DNS e esse servidor estiver respondendo às consultas, isso é um bom sinal de que o problema não é tão grave.
Se a máquina não puder fazer o ping e você mencionou que eles estão na mesma sub-rede, verifique um conflito de endereço IP e verifique se não há erros de digitação na sub-rede, gateway, máscara de rede, etc.