RDP failed to access TS with none-default port

[Guest]

I could not use WinXP Pro to connect to a terminal server (Win2K Advanced
Server) which use a non-default port. The address is something like this:
56.123.47.254:13389. Everyone else in my firm can connect to it. Also I can
connect to any Terminal Server with default port ( i.e. no port number on the
address such as 34.63.12.34). It seems that the problem is related to the
type of PCs. The only two laptops with this problem are HP nw8000, one is XP
Pro SP1 and another is XP Pro SP2. The error message is:

The client could not connect to the remote computer
Remote connections might not be enabled or the computer might be too busy to
accept new connections. It is also possible that network problems are
preventing your connection.

 

[Guest]

Try telneting to that port.
Click Start/Run, type cmd, hit Enter.
Type telnet 56.123.47.254:13389 and see if you receive a succesful connection.
Do you perhaps have some extra firewall/security software installed?
Tried turning off Windows firewall just for the sake of the test?

A.