You'll need to upload in ASCII, not binary, then CHMOD to 755. You should only need public read and execute permissions so 755 is what you want, not 777.
If you need a new copy of the formmail. pl, just search for it and download a new copy; it's a common universal script used for generic forms. It's probably Matt Wright's script or a version of it.
Edit: BTW, you'll need to be sure that the path to perl, the first line in the script, is correct. It's usually this: #!/usr/bin/perl
You'll also need to be sure the path to the sendmail program is correct which is usually this: $mailprog = '/usr/sbin/sendmail';
Just open the original script in notepad or something and compare it to the new copy and make any appropriate changes.
Edit2: Oh yeah, you'll also probably need to set the @referers. This line:
@referers = ('yourdomain.com');
Just change 'yourdomain.com' to whatever is the name of your domain, you may want to include the IP address as well. Separate using commas like this: 'yourdomain.com', '129.23.45.678'. Be sure to include the single quotes at the beginning and end of each referer.