Ok let's step back here for a minute. You say you have VPN enable and
working. What I would do is enable your VPN, make sure you can ping the
remote machine. Use RDP client to connect to that machine.
If you have VPN setup you do not need to open port 3389 on your firewall
because you already connected to your remote network.
As far as why you can't connect to your computer here are a couple things
you can take a peak at.
1. Make sure the PC is turned on
2. Make sure the PC's ip didn't change
3. Make sure that you used port forwarding and pointed
it to right IP
BTW Terminal Services is not, in my opinion, a way to remotly login to a
different network. It's more for doing maintnance within your own network.
Have fun!!!