You can occasionally get deals for ~$15/year for a *nix VPS, and certainly find something usable for ~$8+/month.
EDIT: I wouldn't run anything in production on these boxes, but they are great for dev machines, VPN/SSH proxies for securing open wifi traffic, remote shell, etc.
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.
As for cost, it's pretty cheap - $7.95 for a 512MB Xen.