As steves has already pointed out you may have a LD_LIBRARY_PATH issue you are falling victim to.

One caveat I have to point out. When you execute a script from the command line you may not necessarily have the same shell environment that your CGI environment is going to have. This is where having a really good relationship with your system administrator pays off.

You mention a re-installation: of the scripts to a new environment or was the hosting environment rebuilt?

The last time I ran into the errors you mention was when I installed a new version of Perl on one of my production machines at work. I remember having to recompile a lot of the modules (of course the CPAN ones all and to be re-installed) as well as the locally grown ones.

In any event, checking out the apache logs when you get 500 errors often yields a wealth of information.