Via this WHT offer, NetXServers’ VPS plans start from $6/month Mini VPS with the following spec:
64MB guaranteed/128MB burstable memory
4GB storage
20GB monthly data transfer
CentOS/Debian/Fedora Core/Gentoo/OpenSuSE/Ubuntu
Servers seem to be in Dallas, TX.
Update 2008-06-09: VPS plans seem to be discontinued. When you go to the page it gives you back this blob:
All NetXServers.net VPS plans are being discontinued [...]