The 1&1 VPS1 and VPS2 package turn out to be the same price, if you include the coupon offer for VPS2 - so it's $360 for 1GB RAM.
How about this lunarpages?
http://www.lunarpages.com/virtual-private-server/
You get 512mb guranteed, but it looks like no burst RAM.
Also I've always had shared hosting so I have no idea how "256mb" really works for a website, how would that compare to what you would get with shared hosting?