RDP über Internet auf Terminalserver

Ich versuche über das Internet mittels RDP eine Verbindung auf einem Terminalserver aufzubauen. Das klappt mit einem Client wunderbar und der User kann uneingeschränkt arbeiten.
Sobald ich jedoch aus dem selben Netz oder auch aus einem anderen Netz eine weitere RDP-Sitzung eröffnen möchte, erhalte ich die Fehlermeldung, dass der Client keine Verbindung mit dem Remotecomputer herstellen konnte und das die Remoteverbindung nicht aktiviert ist usw.

Hat jemand dazu eine Lösung ?

Hinweis:
Alle anderen Anwender, die per RDP im Haus auf den Terminalserver zugreifen, haben keine Probleme.
System:
Windows 2003 Server incl. SP2