I think you are pretty close to figure out the missing libraries.
When you straced the lsperld.fpl, you actually traced the cgi-fcgi or whatever the fcgi spawner you used, not the lsperld.fpl itself. You should either let strace to trace children process by adding an command line option, or do something like "cgi-fcgi ... strace ./lsperld.fpl".
Once you master how to use strace properly, you can figure out this kind of problem easily, no matter it is perl, python, or ruby, etc.
Please let me know what libraries/files are missing after you figured it out. :-)