Is it just this one particular script that's not working - or can you not get any scripts to work?
If you have the correct path to perl, the correct new paths to all your data files etc, you have CHMOD 755 and they still don't work then I'm a bit stuck!
You could check one more thing, though...
Log in to the Plesk Server Administrator pages, then click on the domain name where the scripts are being run, then click 'Hosting', then click 'Next'. On this screen, make sure the options for 'CGI Support' and 'mod_Perl Support' are both checked.
I hope that's of some help, but it could well be something else...