Also, could your firewall be blocking TCP port 3389?
Also, you don't need portqry to check for open ports. You can use the standard telnet built into Windows to check.
The syntax is:
C:\>telnet servername 3389
If the port is listening, you'll get a blank screen with a blinking cursor. If the port is blocked or unavailable, you'll get a timeout error.
We need more information about where this remote server is. Is it across a static WAN link, such a T1, or is it over a VPN connection using the internet and two routers? Are you allowing TCP port 3389 to pass through your firewalls? If it's a remote network, are you doing port forwarding to allow TCP port 3389 traffic to be directed towards your server's private IP address?
Again, we need more info about your network and how you're doing the RDP.
Thanks.