Ja ich hab es so gemacht:

perl Makefile.PL
make
make test
make install
make clean

Dann hab ich das Modul manuell nach /usr/lib/perl5/5.6.1/i386-linux kopiert.
und da wird auch gesucht:

@INC contains: /usr/lib/perl5/5.6.1/i386-linux /usr/lib/perl5/5.6.1 /usr/lib/perl5/site_perl/5.6.1/i386-linux /usr/lib/perl5/site_perl/5.6.1 /usr/lib/perl5/site_perl /usr/lib/perl5/vendor_perl/5.6.1/i386-linux /usr/lib/perl5/vendor_perl/5.6.1 /usr/lib/perl5/vendor_perl