I came here today with the same problem. Unfortunately, the clean up utility didn't solve my problem. It requires MS Installer to be working, which is clearly is not working.
I found KB315346 (http://support.microsoft.com/kb/315346). My server is still in the final reboot stage. I've been trying to install a new NIC all day. Hopefully, this will solve my problem long enough to install some drivers for the NIC, so I can get back online.
I'll keep you posted.