That, to me, sounds like an excuse.
The online stats we have at ValveTime.net (
http://www.valvetime.net/) are never much less than yours. And I notice your most online users ever is about 500. Ours is 2,500. When that happened (very recently), our VPS didn't buckle once.
Yet, it only has 3GB of RAM. Not sure about processor cores but I don't think it's as many as 8.
My point is, for your server to be that spec, and for him to be telling you that your server isn't good enough is frankly bull.
We use the Typhoon package at Nimbus Hosting (
http://www.nimbushosting.co.uk/).
Oh. And our VPS hosts
http://www.valvetime.net,
http://xenmediagallery.com,
http://combineoverwiki.com and in addition to all of that it also used to run
http://8thos.com at the same time (we temporarily helped them out while they were between hosts).