If your users are already experiencing slow performance while accessing their own workstations via RDP over VPN, then moving them over to a Terminal Server isn't likely to increase performance significantly. You'll just be moving the source of the data - the amount of data won't decrease with Terminal Server versus your current situation. In addition, to use Terminal server, you'll need to purchase Terminal Server CALs - one for each active connection you want to support.
A few things to check, though:
- I'm not sure if the Windows PPTP server/client support compression. If it does, though, make sure it's enabled.
- If your users are running RDP at high resolutions and/or full color bit depth, they may be able to see some incremental performance gains by decreasing resolution a bit and decreasing color bit depth. These settings are configurable on the RDP client.
- What is the upload speed of your office's internet line? It's possible that you're maxing out your upload bandwidth.
Edit
Comparing Terminal services and VPN are like comparing apples and oranges. They're two different technologies meant to provide solutions to two different problems. VPN (whether it's PPTP, IPSec, SSL, etc) just provides your clients with a secure, encrypted connection from their remote location back to your office network. Terminal Services (which can also called Remote Desktop) provides a mechanism to remotely display and control another system's desktop. With Terminal Services, it's possible for multiple users to connect to a single server, each with their own screen/desktop.
So, for a complete solution, you'll need to employ both some sort of VPN along with Terminal Services. The VPN gets your clients securely connected to your network, after which they can access either their own workstation's remote desktop or your central Terminal Server (if you choose to implement that).
With only 400 kbps upload, it's no wonder that things get slow when multiple users are accessing the connection. Short of increasing your upload speed, there's really nothing that can be done to help this situation unfortunately. Sure, you can investigate turning on compression in your VPN protocol, but that will only lend an incremental gain in speed, not anything drastic.