Have you tried to get the 2nd computer user to send you a remote assistance request?
MSN Messenger / Windows Live Messenger can do this and requests can be sent by email. When you do this both computers poll port 3389 and that lets the routers know where to sent port 3389 traffic.
I have recieved a e-mail invitation from the second computer, but it does not connect. It states the other computer may of closed remote assistance. I know it will work because I tested the process at home with my two computers