If adding the path to the environment or specifying the full path when executing the program doesn't work, then the problem is the path. It's either permissions or some other environment setting that you're doing in your .profile which is not being set in the web server environment.
It's hard to help you any further without more info from you, specifically any/all warnings and errors that your script produces. If you haven't already done so, add these lines to the beginning of your script and tell us what happens.
use warnings FATAL => 'all';
use CGI::Carp qw( fatalsToBrowser );