And what's your upload? Try http://www.speakeasy.net/speedtest/
If it's not that, I'd say it's a configuration issue with the VPN endpoints. What are you using on your end to establish the VPN? Just a session on your machine?
You probably don't know what they are using to serve the VPN on the other?