VPS4Less.de has a minimum OpenVZ VPS package that starts at €3.99 per month (or $5.82 at the time of writing), and you get:
64MB guaranteed memory
256MB burstable memory
1GB storage
2Mbps unmetred (600+GB per month)
Fedora Core, CentOS, Debian, OpenSUSE and Ubuntu
DC is in Germany I believe.