Você não especifica o que "outras máquinas" significa. NAT ocorre em um gateway ou roteador. Se as outras máquinas estiverem em outra rede, conectadas por um ou mais roteadores do que é possível, você está tendo problemas de NAT. Se eles estão na mesma rede, o NAT não é um problema em potencial.
Para começar a diagnosticar seu problema, você deve tentar fazer o ping de uma das máquinas remotas e fazer com que ela faça ping na sua máquina. Se funcionar nas duas direções, o NAT e os problemas de roteamento associados não serão os culpados (é provável que seja um problema de firewall naquele ponto, possivelmente em sua máquina local).