I know this is an old thread, but I have the same problem.
I've tried adding an .htaccess file inside my cgi-bin directory (where Movable Type is) like this:
AddHandler fastcgi-script .fcgi
This does not work.
Test Script:
#!/usr/bin/perl
# Hello World Script
# Filename...