I've just been looking around for ages to figure this out, but couldn't find the answer... so felt compelled to write about it.
I have several Windows 7 machines, all able to remote desktop to each other no problems.
I added two Windows XP machines to the network, and could not remote desktop to them.
Went through all the troubleshooting, and realised they have Windows Firewall enabled on them. So I went in and ticked the box in the Exceptions. This still did not work.
I shortly discovered I could connect if I used their IP addresses, but not if I used their machine names.
I later discovered that if I turned off the firewall completely, the connection worked no issues.
The answer lies in the Exceptions entry for File and Print Sharing. You don't have to tick this box entirely if you do not want to, but there are two ports in there that need to be open for Windows to locate the machine by its NetBios name: 137 and 139.
I realised this when I read the below KB article:
http://support.microsoft.com/kb/842242
It shows that those ports are used by the local machines NetBios name service. So you will have to open up more than just port 3389 in the firewall if you want to connect by machine name.
Regards,
Rob.