Apache2 - Debian (squeeze) - CGI Problem

[Torry Crass <torry_crass@yahoo.com>]

First, if this is the wrong list, I apologize and if someone could point me in the right direction I'd be happy to go there.

I've been fighting this problem for quite a while (on and off for about 3 months now) and cannot seem to get a handle on it.  The short of it is, I'm not able to use cgi/pl scripts.  I've included all the information I could that I felt relevant below.  Errors at top, settings/versions/configuration below.

Any pointers/help are greatly appreciated.

##### ERROR MESSAGES #####

Error:
500 Internal Server Error
Internal Server Error

The server encountered an internal error or misconfiguration and was unable to complete your request.

Please contact the server administrator, and inform them of the time the error occurred, and anything you might have done that may have caused the error.

More information about this error may be available in the server error log.

Apache Error Log:
[Sat Jul 10 14:23:38 2010] [error] [client X.X.X.X] Premature end of script headers: test.pl

##### VERSIONS & CONFIGURATION INFORMATION #####

Versions:
Debian (squeeze) -  2.6.32-trunk-686 #1 SMP
Apache 2.2.15-5
PHP5 5.3.2-1
Perl 5.10.1-12
libapache2-mod-perl2 2.0.4-7

Linked Copy of PHPInfo() (ip's and such removed):
http://pleiades.zymichost.com/

Apache Modules Loaded:
alias
auth_basic
auth_kerb
authn_file
auth_pam
auth_radius
authz_default
authz_groupfile
authz_host
authz_user
autoindex
cgi
deflate
dir
dnv
geoip
log_sql_dbi
log_sql
log_sql_mysql
log_sql_ssl
mime
mod-evasive
mod-spamhaus
negotiation
perl
php5
proxy_html
python
random
reqtimeout
rpaf
setenvif
status

CGI-BIN Location (Debain Default):
/usr/lib/cgi-bin

Executable File:
-rwxr-xr-x 1 www-data www-data      89 2010-06-22 00:05 test.pl

Contents:
#!/usr/bin/perl
print "Content-type: text/html\n\n";
print "hello from Nginx to Apache";

Apache Site Configuration Directive (present inside the VirtualHost brackets:
        ScriptAlias /cgi-bin/ /usr/lib/cgi-bin/
        <Directory "/usr/lib/cgi-bin">
                AllowOverride None
                Options +ExecCGI -MultiViews +SymLinksIfOwnerMatch
                Order allow,deny
                Allow from all
        </Directory>

mime.conf Module Configuration Change (cgi adds handler):
#
# AddHandler allows you to map certain file extensions to "handlers":
# actions unrelated to filetype. These can be either built into the server
# or added with the Action directive (see below)
#
# To use CGI scripts outside of ScriptAliased directories:
# (You will also need to add "ExecCGI" to the "Options" directive.)
#
AddHandler cgi-script .cgi .pl
Options FollowSymLinks +ExecCGI