Hi Carl,
Your shutdown -h command simply means "halt" and "now" means now. This was just an orderly power off of a system
It would seem that you did not setup VPN or you would not be in this pickle. I'll try to help (I run it to alot of locations) but you really need to provide a lot more info.
What version(s) of the Linux kernel are you running?
Can your boxes "see" each other by "ping"? This may not work if your firewall drops ICMP packets, but it is worth checking.
Do you know how to use the firewall configuration tools? You will want to be able to provide more info using them later.
Are you running DNS servers on your endpoints (one or the other or both)?
If you will post this info, I will try to help you.
Bill