Just wanted to post this here because it took me some time to figure it out and couldn't find much about this elsewhere.
I had some problems trying to deploy a Catalyst app on a server where my CPAN (and my own modules) are installed in a local directory handled by local::lib.
I use Apache2 and the app runs as a cluster of FastCGI processes (static setup). Altough the user who runs Apache has the PERL5LIB properly set up in a login shell, somehow Apache didn't see this setting. Turns out that Apache deliberately ignores the PERL5LIB unless you explicitly tell it to use it with a PassEnv directive.
In addition, you also need to pass the PERL5LIB path through to the acutal FastCGI processes so that they are started up in the correct environment. You do that with the -initial-env option to the FastCgiServer directive.
All in all, you should have something like this in the config file for the site:
[... YOUR USUAL CONFIG STUFF HERE ]
# tell Apache to use the PERL5LIB
# pass it on to the fastcgi processes that Apache will
# start up for us (3 in this case)
FastCgiServer /PATH/TO/my_app_fastcgi.pl -processes 3 -initial-env P
The PERL5LIB is setup in the bash profile for the user who runs Apache in my case (using local::lib). You could also substitute PERL5LIB for an explicit path in the above code snippet.