RD Connections lost using FortiClient VPN with IPSec

I work for a small company that has various users spread geographically across the country. They all use PCs running WinXP (one using Vista) and usually using a wireless connection for Internet access. We have an Exchange 2003 server and a Terminal Server running Server 2003.
Users acquire an Internet connection, connect to our VPN using FortiClient 3.0 software through our FortiNet appliance. Then each user connects to the TS via Remote Desktop Connection.
The users are connecting (when able to establish a wireless connection) most often from hotel networks, coffee shops, corporate client sites, as well as from their own homes.
 Right now our issue is with the VPN and RD connections being flaky at best. Sometimes the RDC will freeze up momentarily or entirely, other times a "reconnecting" dialogue box appears and cycles through 20 connection attempts--sometimes reconnecting and other times just dropping. Sometimes the RDC drops, but the VPN connection remains intact. Usually both connections are lost entirely. Usually web browsing is still possible and general internet connectivity is there.
We need some serious help here. Constant interruptions are simply unacceptable to my teammates as well as their clients. I simply don't know what to do. I'm waiting on our hosting vendor to respond, but nothing yet.