Using a VPN has nothing to do with the circuit speed or bandwidth. It has to do with the technology to ensure that the circuit is secure which takes a lot of overhead. Theoritically, you can have VPN using a 56kbs circuit - why I do not know, but you could. It can be set up over almost any of the circuit types - T1, T3, DSL, etc. That is why most VPN circuits being sold are high speed circuits - typically T1's.
As previously mentioned, the handshaking is the determinant in VPN performance. The type of tunneling involved is another determinant - point to point or fully meshed. Point to point is the easiest and the fastest. Fully meshed means that all the circuit points have access to every other point for redundancy. As you can imagine, the overhead involved is complex and expensive in terms of performance.
I used a VPN connection from home. I usually get 28.8kbs and using a VPN with a top line speed of 28.8 is very painful. Reminded me of using AOL with a 2.4kbs modem - oh, the agony!!!! /w3tcompact/icons/eyes.gif I had to use an application which was typically very chatty and constantly polled the main server for status. When I pulled my emails, it would typically take a half and hour to receive 15-20 emails - mostly text messages with a couple of small attachments. If one of those emails had a mid-sized attachment, I could walk away from the machine for an hour and the messages would still be coming in. It was horrible. So much for working from the house with a VPN and a low speed connection.
Terry