That's odd. I just tested FTPing mt-check.cgi up to my server in binary mode instead of ASCII, and even that worked fine. Well, I first forgot to chmod it, and that gave me an Internal Server 500 error. After I set the permissions with chmod 755, I was able to review the output from the cgi file without a problem.
Random debugging ideas:
1) Open the file on the server in a text editor like emacs, vim, or nano to make sure it looks like normal perl code
2) If you're not sure what to look for with suggestion 1) above, type "head mt-check.cgi" (without the quotes) at a shell prompt in your mt directory and verify that the first couple lines are:
# Copyright 2001-2003 Six Apart. This code cannot be redistributed without
# permission from www.movabletype.org.
3) At a shell prompt, type "file mt-check.cgi" and verify that you get back
mt-check.cgi: perl script text executable
4) At a shell prompt, type "ls -l mt-check.cgi" and verify that you get back
at the beginning of the listing.
Also, do any other cgi scripts work for you?