I've had really good luck with thrustvps so far. I found them from lowendbox.com and got 15% off the already-absurd prices forever, so I'm paying $5.06/month for a 512MB box.
It's OpenVZ instead of Xen, but I don't really care; I wouldn't really be taking advantage of Xen anyway. (And they have Xen for a couple bucks a month more.)
I have no idea how its performance compares to Linode, AWS, etc, but stability has been fine so far, after 3 months. I kind of expected to have downtime by now since it's so cheap, but pingdom tells me there's been none.
If you're looking for a cheap VPS so you can run relatively unimportant things (ie. not your startup, unless it's just a side project that isn't bringing you any money yet), it's a good choice.