This is just a good-to-remember for myself.
When Apache reports this error with your CGI program, a script most of the case, you need to understand, or to know what the error message means, or what Apache complains about. Which I found many posts that I came across talking about the error do not really explain.
As you know, output of any CGI program must take the following form.
HEADERs
e.g. Content-type: text/html
A blank line
The payload. Normally a <HTML> element.
Apache complains with the message that the output fails to take the form.
Luckily, for the Perl script that I had the problem with, it was rather easy to locate and eventually remove the issue.
This was the good reference. http://www.linuxjournal.com/article/1367 It explains how to run a Perl CGI script from the command-line.
The point is that when you run it, it waits for input, for any possible POST payload. You indicate the end of the input with a control+D. Then it runs and you can see the output on your terminal. Once you get it, locating the issue should be (normally) straightforward.
In my case, the issue turned out that an external executable called from the script ends abnormally, and therefore corrupts the output.