bitcoind's dependencies are very minimal
It should run on just about any proper Linux distribution, including all of the ones you mentioned
not the CentOs, it is likely to be very old-but-stable, and would therefor not work.
Gentoo it not recommended, it requires too much memory, becuase it build anything from source. more memory -> bigger price
Debian, we already tryed that one, it did not go well.
fedora or opensuse, i don't know they might work.
i recommend ubuntu, if its 10.04 LTS, or newer.
CentOS version 6.0 was announced and released on July 10th, 2011; I'd hardly call that old.

It runs a modern kernel version and very adequately supports every dependency of bitcoind.
Gentoo requires no more memory than any other operating system running an equivalent kernel and software payload, and any of their stage3 tarballs does indeed contain all the libraries that bitcoind depends on without any need for compilation or recompilation of anything existing or extra
Debian, likewise, should have no trouble running bitcoind -- what is your experience with it? From a fresh installation, if bitcoind doesn't run right away, it should not take more than two minutes to diagnose and resolve the issue to get it working properly
I don't mean to sound rude, but if these aren't working for you, you're doing it wrong

I'm sure my VPS provider has not yet updated their CentOS version to the latest.
I might give Gentoo a try...
Debian 5.0 was a disaster. The only version of bitcoind that I could get to run was a modified version of 0.3.22, and I tried for like a week with the help of this forum to get it to work. I've given up on that front. You only need to read through this thread to see what happened with Debian.
And of course I was doing something wrong. But no one here could help me to do it right, so obviously, it's not just my head that its over.
Believe me, I'd love to use linuxcoin, but the VPS doesn't allow me to install my own OS - only the ones that they have listed.
I'll try Ubuntu first though, thanks for the advice kokjo.