Das mit dem fehlenden "lib" basiert noch aus alten Perl-Tagen, als h2xs eine etwas andere Ordnerstruktur angelegt hat. Mit Perl 5.10 wird hoffentlich eine neue Version von perlxstut mit ausgeliefert (im perldoc-SVN ist jedenfalls eine korrigierte Version enthalten).

Aber danke für die Hinweise!