Let me guess you are running Debian stable distribution AKA "potato" right? Well the name of the perl package changed between potato and the upcoming woody distribution. perl != perl-5.005 so to maintain consistency, the packaging system will not let you proceed until you choose one or the other.

Your choices are:

• Upgrade to woody. It will be released Real Soon Now and has a lot more uptodate stuff than the by now rather ancient potato including perl 5.6.1.
• Recompile the libmail-sender-perl package for potato, correcting the perl dependency. Not too hard though everydevel doesn't seem to have to have included the source package. The maintainer is listed as Jay Bonci <jay@bonci.com> He could give you the source or perhaps he has a potato package lying around.
• Just install Mail::Sender from CPAN. The drawback is it will not be visible to the Debian packaging system but it is the easiest way forward short-term.

If you still have questions the Debian User mailing list <debian-user@lists.debian.org> is probably a better place to ask than here.

--
જલધર