I had this issue and realized that the file cgi-bin/php-fcgi had no execution rights.
It had 644 mode while is should have 755 mode.
Setting the correct mode was impossible (probably because the file was opened or sth), so I copied that file from another domain directory where it had proper rights already set and that fixed everything.