I have been running cento for a while and I am switching to Debian.

The problem I had with Centos is that if you need a recent version of a software the chances that you need to use a non-official repository or even have to compile from source are pretty high. The whole concept of CentOs is that you use only yum and you are very very confident that everything will work together. Right now, CentOs is stuck at php 5.1.6 and more and more projects are requiring php 5.2+...
I chose CentOs in the first place because that was what my former shared webhosting (lunarpages) was using. Now, I understand why they use it: it is really stable and since their customers do not need cutting edge versions of the major software, it is a very good deal for them.
I am moving to Debian because (1) I found a gerat tutorial to setup my mail server on Debian (2) this is the lightest distro offered by linode (3) php 5.2.6 (4) g++ 4.3.2 versus 4.1.2 in Centos.
Hopefully, I will be able to move all my linodes to Debian fast because I believe it is much better to have all its linodes running the same distro.
I can still imagine many situations where Centos is the best distro though.

There is a great tutorial on how to upgrade php to the 5.2+ on CentOS --> http://www.shestakovsky.me.uk/blog/?p=20

Please do not forget that you have to choice either a cutting edge system (Fedora?) or something more stable (CentOS) or something extremely stable (Debian Woody/Sarge). There is almost no compromise.

Personally, I like RPM based Linux so my choice would be CentOS or Red Hat Enterprise. For laptop/desktop I like Ubuntu or Fedora.

Remi's repository is great and I installed php 5.2.10 easily.
But the day after, I typed "yum update" and I got php 5.3, which is a totally different beast with numerous breaks and nothing was working properly anymore The solution was to add uninstall php, add something like exclude=php*-5.3* to remi.repo and install php again.

That is not extremely stable, that's extremely outdated or maybe you mean by stable 'fossilized'

Currently, Debian Oldstable is Etch and Debian Stable is Lenny.