A mensagem de erro parece implicar que a porta não está disponível para esses sistemas.
Talvez haja um firewall de camada 2 filtrando as conexões (ou um firewall no servidor). Verifique isso usando telnet (do cliente, abra uma janela de comando e digite telnet <serverip> <rdpport>
). Se ele não responder com um banner anunciando o serviço RDP, o problema estará na rede, ou seja, um firewall de algum tipo, em vez do aplicativo.
Se a sua rede for mais complexa, também é possível que, enquanto os computadores estiverem na mesma LAN, eles estejam em sub-redes diferentes e haja um firewall regular bloqueando as conexões entre as sub-redes. Você pode verificar isso usando o traceroute. Se houver mais de um salto, ou o primeiro salto não for o IP do sistema remoto, você estará passando por um roteador - provavelmente com um firewall impedindo o acesso.