The RPM format was often accused to generate a so-called «dependency hell», pretty much like the «DLL hell» in Windows.
The DEB format is praised to be more intelligent, but I actually felt it's good because of the associated tools: no, not dselect and dpkg, but apt-get (and apt-cache, apt-file) or Synaptic. To make things even better, aptitude is much smarter in solving and fixing broken dependencies.
So they say.
As for myself, I believe that no matter how smart a tool or a file format specification can be, if you don't set the dependencies properly, you're going to hell anyway.
Full Story [2].