PREFIX sets a poor default for LIB, so I use

perl Makefile.PL PREFIX=~ LIB=~/lib/perl5   (Old and new MM::EU)
[download]

or the equivalent

perl Makefile.PL INSTALL_BASE=~             (Newer MM::EU only)
[download]

and set PERL5LIB to

~/lib/perl5
[download]

If you used

perl Makefile.PL PREFIX=~/perl_mods LIB=~/perl_mods/lib/perl5
[download]

you'd set PERL5LIB to

~/perl_mods/lib/perl5
[download]

With the options you *did* choose, it seems you should be setting PERL5LIB to

~/perl_mods/lib/site_perl/5.8.4
[download]

or maybe just

~/perl_mods/lib/site_perl
[download]

Don't forget to use /home/... instead of ~ in places where ~ isn't expanded.

If you're still having problems, please provide the output of perl -V (uppercase "V"), if only the part near the bottom that lists %ENV and @INC.