Also nach make install liegt das Modul in

/usr/lib/perl5/site_perl/5.8.0/

im Verz. Dev (Obiges Vz. ist auch in @INC enthalten)
Die Datei heisst MySQLDB.pm.
Der Konstruktor heisst auch ganz sicher 'new'.

Ich habe jetzt noch mal einen einfachen test gemacht:

/home/test/mod/testmod.pm

/home/test/test.pl

Und die Pfade sind wie oben.

h2xs -X -A -n testmod
perl Makefile.PL
make
make install
../perl test.pl

und dann kommt wieder

Can't locate object method "new" via package "testmod" at test.pl line 3.

Also jetzt geht es gar nicht mehr.
Da muss doch noch was anderes falsch sein?