When using FTP, it is very important to upload script files (e.g. .cgi and .pl) in ASCII mode. FTP clients will give you the option of uploading in ASCII, binary, or "auto." If "auto" is selected, then make sure .cgi and .pl are considered ASCII files by your FTP client. Scripts will not execute properly if they are uploaded in binary mode.
Be sure to follow the directions included with the CGI script.