I run a small (100 client) WHMCS setup on a 256MB/Xen account (I am not a fan of OpenVZ, personally)
but, do consult your tech guru, unless you are this person, and look at pricing.
I use one of these two mentioned, which I will detract from mentioning since it can get pretty polemic when you address such issues, but find that these two providers below tend to be the "top recommended" and I have had good enough service/experiences with both that warrant a recommendation:
VPSLink (http://www.vpslink.com) -- they have a coupon code until the end of the month, too, I think.
and:
Slicehost.com -- they allow custom images to be run, so this might be of interest for someone.