Myślę, że możesz spróbować wyłączyć wszystkie zabezpieczenia na chwile na obydwóch kompach, oraz możesz też spróbować zmienić port przez, który łączy się program (dopisujesz go po numerze ip, po dwukropku np. 192.168.1.1:1234). Sprawdź też konfiguracje rutera, jeśli go masz. Często w firmwarze są włączone jakieś firewalle i inne baziewia, spróbuj je wyłączyć. Spróbuj też ustawić przekierowanie portu 3389. Jeśli nie macie rutera (wątpie), lub jeśli to nie w tym problem, spróbuj zadzwonić do usługodawcy internetowego i tam poprosić o przekierowanie portu. Często uslugodawca blokuje niektóre porty, dla bezpieczeństwa. Wpisz też w pomocy systemu Windows hasło: Rozwiązywanie problemów z Pulpitem zdalnym . Jest tam kilka obiecujących wzkazówek.
Jeszcze jedno: jakiego dokładnie systemu dotyczy problem? Tzn. na jakim systemie uruchamiasz ten pulpit zdalny?