Spent a few hours discussing dm with niemeyer last Friday. dm is a python-based modular dependency analisys tool for RPM-style packages with helpers to detect and fix incorrect, stupid, or brain-dead inter- and intra-package dependency issues. You don't know how messy your packages are untill you start to chart them.
Once you start to use APT, correctness of the dependency tree becomes critical. We (at conectiva) tried to pay special attention to this issue and to fix existing problems. We thought we were mostly clean, but dm shows us otherwise.
Also our experience with APT helped us to understand the reasons of many seemingly arbitrary entries in the Debian packaging policy: APT ditactes that way. Tests on our policy-enforcing autotester should be improved to block packages based on dm's analysis.
And this, after all, seems to be a worthwhile to learn python (and try to get used to the annoying braceless syntax). The results of the preliminary dm prorotype are already helping me on the redesign of some important packages, where dependency mess should be kept at a minimum. Let's see how it evolves...