I'm with Tagadab for my hosting (VPS) and I'd recommend them to everyone. Their support is simply outstanding. Yesterday, I made the switch to Ubuntu 10.04 LTS, because 8.04 was driving me mad (with the lack of recent software). The first problem was that I couldn't update without running out of memory. Not a difficult problem to fix, I just added some (512mb) temporary swap:

$ sudo dd if=/dev/zero of=/swap count=524288
$ sudo makeswap /swap
$ sudo swapon /swap

The second problem was a bit bigger. After the upgrade had finished, it restarted and I couldn't get on with ssh. I emailed tagadab telling them my problem and they emailed back saying that it was because they needed to update the Xen kernel on their servers to support 10.04 and that my virtual server would turn on once they had done this. I was a little sceptical, but I waited a little while whilst they worked tirelessly to fix the problem and low and behold it worked perfectly once they had completed the work. I went with them originally because they were affordable and there support for 'potential customers' was good, but now I can vouch for the fact that there 'actual customer' support is top-notch too. If you're thinking of hosting a website and you want more than just a few static web-pages, look no further.

(I want to make it clear that I don't work for tagadab and they haven't paid me for my testimony, I'm just a happy customer)