"Page cannot be found" (Error 404) is a webserverism - that is, the webserver cannot find the file/cgi. At this point, it is unlikely that Perl has been invoked, and hence it's probably not a CGI-related problem.

Might be worth checking with the hosting provider/sysadmin - they're not running IIS by any chance, are they?