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
