After having trying Fedora and Ubuntu, I got back to Debian/sid (in fact I never erased the
partition). Even in unstable form, I find debian extremely resilient to bad packages, and
aptitude is the software I miss everywhere else.
Aptitude marks all dependencies of a package you install as "automatically installed", which
means if you uninstall the package, all those unused dependencies will be uninstalled too. Its
conflict resolution system is far more advanced too. All in all, aptitude makes apt-get (and
even more yum/rpm) look like a primitive toy in comparison.
Sure, Ubuntu has aptitude, but it can't really be used here: their update tool has some
knowledge needed to do some cleanup on each version update, so in a sense they perverted the
dependency system by adding parallel information somewhere else.
Try aptitude for a while, and you'll never get back to something else ...