Don't know if this will help at all or not. And I don't really understand how this helps, but I read on another site that updating the video drivers would help. I didn't think so but had tried everything else. My scenario is slightly different in that both machines were on the same network (behind the same firewall). Used to be able to remote to XP machine from another XP machine, after installing Windows 7 could not connect to XP machine. All settings were right (virus scanners, firewalls, remote connect settings). So I ran Windows Update on both machines, making sure that the video driver updates were included. After reboot, connects with no issue.
Before when I tried to connect the progress bar would show for a half a second then disappear, then nothing. No other messages or warnings.
So if you want to give it a shot, again don't know exactly why this would work, but it seemed to do the trick for me. Call me crazy if you want.