Rather than specifying the full path to each of your executables, you could explicitly set $ENV{PATH}. If ps2pdf doesn't really live in /usr/local this would actually make your program suddenly work :-) You should be running with taint mode turned on (#!/usr/bin/perl -T) anyway which would force you to be explicit about your path.

I'm obviously just guessing about your path being wrong. Something else that might be a factor is that your server may be setup such that CGIs run in a restricted environment which doesn't have access to /usr/local (for instance).

Hope this helps,