Anytime text (via std or err output) is returned from a cgi it goes back to the browser.
If any text precedes(it usually does) the header ("Content-type: text/html\n\n" in the case of an html page) then the browser will think something is wrong. (It will think it is receiving a bad header.)

On the possibility of permissions problems. I have a few hosted sites that prevents any cgi from executing if the directory the script is in has potentially insecure permissions. (group/other read/write needed to be turned off, this might apply to the script too)
It may help, it's caught me several times.