What about perl-bug #279232?
I just once again go through a woody->sarge dist-upgrade and once again,
#279232 bit me (didn't have my patched perl packages at-hand).
To shortly describe the problem:
under some circumstances, perl-base and perl-modules are not updated
together, so maintainer scripts using anything from perl-modules fail,
because it's installed in another version than perl-base (5.6 vs. 5.8).
it could be "fixed" by introducing a versioned pre-dependency of
perl-modules on perl-base while letting perl-base conflict with too old
perl-modules, which forces apt to update both packages together; this
combination may be highly unstable (conflicts+pre-depends is a loop-like
construct), but results in the right behaviour.