There have been a flurry of recent posts on the "dependency problem", kicked off by this thread about Moose on Perl Monks. Chris Prather defended Moose dependencies and Dave Rolsky added a rant and a meditation about dependencies in general. In the latter article, Rolsky makes a comparison to Debian and constrasts the "binary-only" installation of Debian packages to the "source plus tests" approach of CPAN. I think the parallel to Debian is apt, but for the wrong reason.
As I see it, the problem with CPAN dependencies is simply the implication of a long dependency chain on stability. What Debian has that CPAN does not is a clear delineation between stable, testing and unstable repositories. In this paradigm, CPAN is an unstable repository.
Uploaded distributions are immediately available globally as fast as the CPAN mirrors can replicate. Unless an author chooses a "dev release" version number (1.23_01), the new distribution also becomes the default version for anyone installing one of the modules in the distribution. Even though dev releases are possible, on CPAN, the author chooses the level of stability to signal and it's completely arbitrary, without any connection to real-world results.
With Debian, the end-users get to pick the stability they want to trade off against frequency of bug fixes and new features. On CPAN, end-users have to work a lot harder to accomplish the same thing. This is why long dependency chains make people nervous: there are many more things that could suddenly, unexpectedly, become unstable.
Dave Cantrell's CP5.6.2AN project is a step in the right direction, providing a limited CPAN that only indexes modules that have passing test results on a particular version of Perl. It introduces a new CPAN paradigm much more like Debian, with a CPAN repository containing distributions with some known degree of stability.
This approach could be extended or made more strict: perhaps a distribution only enters a repository if it passes all tests using dependencies already in the repository and if all things in the repository that depend on it pass their tests with the new distribution as well. Going further, distributions might specify dependencies with an exact version, not a minimum version. ((That might also imply a change from specifying prerequisites as modules ("Foo::Bar") to specifying them as distributions ("Foo-Bar-1.23"), since module version numbers need not change, but distribution version numbers do.))
Bringing this full circle, Rolsky suggested that maybe Perl's culture of testing is part of the problem, but I think Perl's testing culture is part of the solution. Things like CPAN Testers and cpandeps give us hard data on what works and what breaks. And if we know that, we can tackle the stability problem, and then the dependency problem will go away.