On the Windows taskbar, click the Start button
Choose Run
Type "C:\Program Files\Microsoft Office\Office\Excel.Exe" /Automation (include the quotes) -- adapt to fit your path.

If your error disappears, there is either an add-in or a (hidden) workbook that is loaded upon XL's start, which is causing problems.

Try locating the XLSTART directory, move everything from there.
In XL: Tools, Addins, note the ones checked and uncheck them one at the time, each time restarting XL
In XL, Tools, options, general. Check if a path is entered after "Alternate startup file location". Clear it.

Another option is to open XL in Safe mode:
"C:\Program Files\Microsoft Office\Office\Excel.exe" /Safe

Also, you might try:
"C:\Program Files\Microsoft Office\Office\Excel.exe" / Regserver

Another possible problem is a corruption of your toolbar customisation file:

Locate all files with extension .xlb
Rename the extension(s) to something like .old
Now try and start XL again.