I am using Ubuntu and I have come across the same problems. If your lucky the module is already bundled as a package and you can install that. If not, I try to use CPAN. The problem is sometimes finding all the dependencies(underlying libraries) to get packages installed can be difficult.

I have also installed a separate version of Perl due to a Class::Std problem with the default system build. Luckily my application had relatively few library dependencies but sometimes you are still stuck trying to identify and install the correct libraries for modules.

My recommendation.

1. Install debian packages first.
2. If the module is outdated, upgrade via CPAN. Worst case you can delete the files manually and reinstall the debian package.
3. Install via CPAN. Worst case, you spend time finding the packages that are needed to install the libraries you are going to depend on.
4. Extreme case, you have no options, install a separate version of CPAN. Change the search path for the account(s) that will use the newer version of Perl. God knows what you would break if you replace the default perl executable.