I've been playing with RackSpace Cloud lately and so far I've been quite impressed. The price is quite competitive, the network seems quite stable and performance is no issue. Plus: persistent storage in the cloud, out of the box! Awesome.

The support has been good (I had a routing issue on privatenet interfaces between two servers, which I was certain was either at the network or hypervisor layer and not my firewall. The engineers and I ran through the usual tests til it was assumed a hypervisor routing issue with this particular guest, which a reboot of the guest fixed).