I agree with BigMacFU, VNC is a good product and its free.

Since I have Windows XP Home Edition (which does NOT allow you to use Remote Desktop with it), VNC was the next best alternative. Easy to setup and serves its purpose well.

Link: http://www.realvnc.com

Unfortunately I don't have any experience with Remote Desktop for the above stated reason. Judging by your symptoms, it sounds like you're running into a Security/Firewall issue. You may want to try and google a FAQ or Troubleshooting guide in regards to Remote Desktop if you still wish to purse it v.s. VNC.