I would check some of the following:

• Ownership and/or permissions issues
  Just because you're able to telnet in and execute a program, or read a certain file, doesn't mean that your web server will be able to do the same. Typically web servers run as a restricted user (such as "nobody") so that they can't be tricked into overwriting files in important places, or reading something they shouldn't be able to read. Check to be sure your script has appropriate permissions (typically octal 755) to be run by the general public. Perl scripts should be executable *and* readable.
• Current working directory
  Probably not an issue in this case, since your web.templates file is in your cgi-bin directory and you're explicitely specifying the path to your other binary. In many cases, though, this is an oversight. CGI scripts are typically executed with a CWD of the CGI directory.
• Environment settings
  If your script depends upon certain environment settings to execute correctly, be sure those are set up or worked around in your CGI script. Specifically, if your script executes other apps or programs in your path, be sure your PATH is set up correctly (and explicitely, don't just append) to locate these other scripts, or specify an absolute path to the other binary you wish to execute.
• If all else fails, check your error logs
  Most binaries print things to STDERR when they fail. If this is running under your CGI script, you may not see the error messages in your browser (though if you're using the CGI module, check out CGI::Carp).