I assume use lib loads the module at another time than -I
Testing will show that -I and use lib does exactly the same:
$ perl -IDoc -Ilib -e 'print join(":", @INC), "\n";'
Doc:lib:/usr/lib/perl5/5.8.3/i586-linux-thread-multi:...
$ perl -e 'use lib qw(Doc lib); print join(":", @INC), "\n";'
Doc:lib:/usr/lib/perl5/5.8.3/i586-linux-thread-multi:...
So your problems must stem from something else - probably that the current directory is not what you expect when running under mod_perl.
Try using absolute paths in your use libs.