This sounds like your script is not in a directory recognized by your web server as a CGI directory (such as /cgi-bin/). If you're attempting to put Perl scripts anywhere in your document hierarchy, be certain your web server is set up to handle files of that extension as a CGI script. For example, with Apache, place this in the relevant <Directory> or <Location> blocks, or if you don't care to localize the effect, anywhere else will do:

AddHandler cgi-script .pl
[download]

The problem stems from the fact that your script may be being interpreted as a plain document, which cannot be POSTed to. You have to tell the server to interpret that file as a CGI script instead of a document, which involves placing it in a directory set up for CGI scripts, or telling the server that documents with that extension/MIME type should be treated as CGI scripts.