Problems with Terminal Server over VPN

[Wanabe]

I just had my ISP bring up a VPN between 5 sites. Now I'm having trouble using Terminal Services over the VPN from the romote sites. I know that everything on my firewall is configured correctly (port 3389 open, etc.). Actually have been using my firewall configured as is with no problem prior to bringing up the VPN and according to my ISP I should not have to reconfigure anything. The firewall does have VPN passthrough capabilities.

What's happening is when someone tries to initiate a TS session remotely, you can see the server attempting to create the session in Terminal Server Manager. Then, for whatever reason, the session times out. I can't seem to figure this one out. I even tried it after turning TS Encryption to Low and still got the same results. The remote clients are definitely hitting the server but no go.

Any thoughts appreciated.

Thanks,
Wanabe