If you get an message box with this warning when trying to start Microsoft Office Excel try to restart the computer. This is what has helped for me. Not sure about the reason that this happens though.
If trying to run EXCEL.EXE directly:
"C:\Program Files\Microsoft Office\Office12\EXCEL.EXE is not a valid Win32 application."
If trying to start with an Excel shortcut:
"This file does not have a program associated with it for performing this action. Create an association in the Set Associations control panel."
This happened with Excel 2007 and Vista SP1.