This might be a little too basic, but in case it helps someone:
Be aware that it can happen that you VPS is in a different data center than the (shared) Mysql server (Los Angeles / Virginia). In this case, of course, the performance will suffer a lot. It happened to me, after migrating from shared to PS.
You can check this (and ask for consolidation) in the control panel (Status->Data Center)