Hosting service can’t handle wp2 mysql demands

My pcmike.com site has been plagued with frequent short crashes since we put it up after Christmas. My hosting company said there were no problems and that everytime they checked the site was working. Finally today, they found an issue and sent me the following:

“Mike it is in fact your domain that is slowing down the server and finally crashed it this morning.
It uses too much mysql resources – more than a shared server can handle.
Looks like you are getting much more traffic to your site before.you can have a dedicated server only for your website but then it will be about $220/month.
Otherwise you may want to consider a virtual private server which we don’t offer. it is relatively cheaper. (around $40-$60/month.”

Anyone had similar issues? Any suggestions for a new hosting service with reasionably priced virtual private servers? Especially someone who will help me do the transfer.