I added use lib "/usr/local/lib" to my script

This won't help here, as this only controls in which locations Perl will look for modules and their immediately related .so files. The secondary library dependencies have to be resolved/loaded by the system's dynamic linker (ld-linux.so on Linux), which has its own search path (LD_LIBRARY_PATH) and other facilities to control what to load from where and when (see "man ld.so" for details). In other words, as Sinistral suggested, one option would be to set/add /usr/local/lib to the LD_LIBRARY_PATH environment variable.

A different option would be to link CRFPP.so statically against libcrfpp, but in this case you need the .a (archive) version of the library (which is probably available as well). See Re: Real Static Modules for how to achieve that when building the module yourself. In some cases this makes sense, in particular if you cater for easy deployment.