I assume you're trying to connect to an XP box, over a LAN, right? RDC will only work with XP/2000/NT.
There is an option on the Windows system that has to be turned on (off by default) to allow a remote connection. I don't remember where this is, exactly, but you can probably find it in a search on Microsoft's site or Google.
As for Mac OS X's "Connect to server...", did you make sure you have volumes shared on the Windows laptop? And using the format smb://WORKGROUP;ComputerName/Driveletter? You /should/ also be able to simply browse for it and see it under "Network" in the Finder, or when you click "Browse" in the "Connect to server" dialogue. This doesn't always work for me, which is why I just type the SMB address manually every time.