Sounds to me like you are not printing out an htlm header of any kind. Try putting
use CGI qw(:standard);
at the top of the CGI script. This will send a standard head to the browser. If you still get an error post a copy of the script.