If you have an Excel heavy group of users, you will likely come across this issue. This happens when someone merges an existing excel file with another one, creating a super excel file that has links and formatting all over the place. When an excel workbook has too many different combinations of formatting, it freaks out and you get the error message above when you try to change formatting of a cell.
Fear not, there is a fix:
Download the .Net4.0 XLStylesTool
This file cleans up the offending excel file by cleaning up whatever nasty bits of information are corrupting the data. I’ve tested this tool, and it looks like it only cleans up formatting, leaving all data and formulas alone. After running the tool, the file became editable again!
-Dexter
source: http://support.microsoft.com/kb/213904
applies to: Excel 2007 files (all files ending with .xlsx) format