I also had a problem like this at one stage. You'll find it here.
This is most probably a MIME error. Are you using CGI.pm to send create the HTML or are you just printing out your own. Sometomes servers can be fussy and don't accept your own. And it is also very easy to include the Content-Type: text/htmlline.
Make sure that your script is in the cgi-bin folder of your server and that it has been set as and executable chmod 755
Also if in future you could supply us with a sample of the problem scripts we could help alot more.
Hope this helps