Need a new hosting co. and advice over mysql issues

My pcmike.com has been plagued with short but several-times-a-day server crashes since we upgraded to WP2 after Christmas.

For two weeks, my hosting company basically ignored my e-mails seeking help. The other day, they claimed I was the only one having an issue and that every time they checked, the site was up.

Finally, this morning, after I sent them time logs of the outages, they sent me this:

>>>>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 tyhan 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<<<<

Any one else having these problems?

Does this sound like a reasonable explanation?

Most importantly, any suggestions on a hosting company with a good snd reasonably priced virtual private server package… especially one that would do the import of my existing site????

Thanks in advance for your help.