If you don't mind using a UK based host, have a look here - http://www.eukhost.com/vps_linux.php
I can't afford a VPS yet, so I have a Linux reseller package with 2 fixed IP's them running on CentOS. So far I have had 100% uptime, and the tech support is very good, fast and knowledgable. I haven't had anything they couldn't fix, including some stupid things I broke myself! The stuff that comes with the Reseller package is excellent, and the VPS is even better. I did quite a lot of research befoe I picked them, and went with the best compomise between price, features and what their forums said about them.
You can see a couple of the sites I host here: