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.