Thought I'd write this up for googlability and my own future reference:

Other than the reasons outlined in the Apache FAQ, the error log message "Premature end of script headers" for a CGI script (in my case a Ruby script on Dreamhost) can also mean that the directory containing the script is world-writable.

So folder permissions like drwxr-xrwx can cause this error. chmod 755 mydir would change those permissions to drwxr-xr-x and all is well.

I suppose Apache/suEXEC takes issue with running stuff that any evil user can edit.