what it really wanted was DateTime/Format/Mail.pm

sudo apt-get install libdatetime-format-mail-perl

Those module versions will always lag behind the current ones, sometimes significantly, but they should always play nice with Ubuntu's Perl installation (that's the whole point). If you want to install a bunch of custom CPAN modules, I'd recommend a Perl built just for that in /opt, where you can experiment and it can easily be clobbered and re-installed in case things do happen to get messed up. Either that, or install all modules locally, e.g. local::lib. A messed up system Perl can be tricky to pick apart and revert to a clean state. Also remember that there are Perl scripts that are part of other Ubuntu packages which rely on a working system Perl.