The first step would be to make the problem visible - show the dependency summary at the cpan search page along side the stars from the reviews. This is a small technical change with the immediate effect of making the installation of modules much less a frustrating fight with an invisible enemy. But what would be more interesting, is the second order social consequences of it because CPAN authors would care more about the installability of their modules.
Comment on Re^3: Perceptions of Perl - views from the edge