I know it doesn't help you now, but my buddy and I are set to launch a hosting company in January. We plan to offer an excellent price to Cubecart users because we love it so much. Matter of fact, we are going to run Cubecart as our store to buy our hosting packages. If you have a more immediate need you can just download a small web server and install it locally on your PC with php/mysql. You can do this in Windows too. Its a bit to type out how to set it all up and configure it....but there is a cheap webhost that I use that is as reliable as it gets.
Check out www.stpwebhosting.com (its about $5 US per mo)
Its only 25mb of space, but my store only has images for the products I carry. (3mb used)
I won't reveal pricing for our service just yet, but look for Brooky to make an announcement as we offer up Cubecart users a big discount.
Stay tuned, it will be worth it.
-investr
Webhost I use