Seen this on a number of different hosts and the only thing I've been able to suggest is to consider changing over to a linux based host.
This happens on NT IIS servers running FastCGI. The phpinfo runs fine. 2.3.2 returns the CGI error, and 2.3.1 will display the initial installation screen (not properly formatted) asking for the blog/email info but after enter that information, it will return "HTTP Error 404 - File or directory not found. Internet Information Services (IIS)"
Here's an example phpinfo experienced recently:
------------------------------
PHP Version 5.1.4
System Windows NT D100 5.2 build 3790
Build Date May 4 2006 10:30:29
Configure Command cscript /nologo configure.js "--enable-snapshot-build" "--with-gd=shared"
Server API CGI/FastCGI
Virtual Directory Support enabled
Configuration File (php.ini) Path C:\WINDOWS\php.ini
PHP API 20041225
PHP Extension 20050922
Zend Extension 220051025
Debug Build no
Thread Safety enabled
Zend Memory Manager enabled
IPv6 Support enabled
Registered PHP Streams php, file, http, ftp, compress.zlib
Registered Stream Socket Transports tcp, udp
Registered Stream Filters convert.iconv.*, string.rot13, string.toupper, string.tolower, string.strip_tags, convert.*, consumed, zlib.*
Zend logo This program makes use of the Zend Scripting Language Engine:
Zend Engine v2.1.0, Copyright (c) 1998-2006 Zend Technologies
with Zend Extension Manager v1.0.11, Copyright (c) 2003-2006, by Zend Technologies
with Zend Optimizer v3.2.2, Copyright (c) 1998-2006, by Zend Technologies