cpanm -v should show where it's installing the module, and you can use perl -V to see @INC where Perl is looking for modules. Perhaps you have more than one Perl installation on this machine (perlbrew?) or you're using something like local::lib?

Update: Ah, it does seem the distro is at fault here. See swl's posts.