The libs in use lib don't need to be in PERL5LIB nor in PATH. Relative paths in use lib are not relative to the script itself, but to the current working directory. So either the script itself changed its current working directory, or you're calling it from an unexpected location (e.g. you've symlinked the script but not the library directory).

For the frequent situation where you want to have the libraries relative to the script, FindBin is a convenient solution. Directly from the synopsis:

use FindBin qw($Bin);
use lib "$Bin/../lib";
[download]

Edit:Now pointing to perldoc instead of CPAN, where a search can give different results.