On my Gentoo-box, whenever I get into Perl-related trouble on:

emerge --newuse --deep --update world

I try:

perl-cleaner --reallyall

…that solves most situations:)