Problem installing 2.6.1 — getting a FastCGI error

Hi. Hoping someone can help me because i’m tearing my hair out.
I have probably installed WordPress hundreds of times, but have never been stumped like this…

When I visit the normal install page I’m getting a ‘500 Internal Server Error‘, and the following two lines in my error log…

Connection reset by peer: FastCGI: comm with server "/var/www/fcgi/php-cgi" aborted: read failed

FastCGI: incomplete headers (0 bytes) received from server "/var/www/fcgi/php-cgi"

After a little fiddling with the error display, I managed to get this further error to come up…

WordPress database error Table 'MY-DATABASE-NAME.wp_options' doesn't exist for query INSERT INTO wp_options (option_name, option_value, autoload) VALUES ('cron', 'a:2:{i:1219260520;a:1:{s:17:\"wp_update_plugins\";a:1:{s:32:\"40cd750bba9870f18aada2478b24840a\";a:3:{s:8:\"schedule\";s:10:\"twicedaily\";s:4:\"args\";a:0:{}s:8:\"interval\";i:43200;}}}s:7:\"version\";i:2;}', 'yes') made by add_option

I would assume from the first two errors, that this is something to do with my server rather than wordpress, but my hosts seems to think there is a problem with the code.
Can anyone give a little clue as to what code I should be looking at?