Up until a couple days ago, I had no trouble at all with my server from redwoodvirtual.com. A couple days ago, the server stopped responding, and they took an unacceptable amount of time to respond to my support email. That hasn't been my experience with them in the past, so I'm still giving them my recommendation - just not as enthusiasticly as I would have before.
vpscolo is excellent service and excellent price.
I've never had to wait more than 7 minutes for a service call. I've just requested a security and general config check- they're doing it as we speak, an hour after I placed my request, at no charge
There are providers out there that offer VPS plans for as low as $14.95. That low of pricing does not include a control panel most likely, and are probably run on a freeware/gpl VPS system--such as UML. The cheapest you will find for a Virtuozzo based VPS should be $20. For you $40 budget, you should be able to get something decent, and with the control panel of your choice.