I have recently been getting messages about “too many different cell formats”, particularly when saving a 2007/10 format file as Excel 97-2003 format. Some searching revealed that the source of the problem was a bug that caused unused styles to be copied when copying data between different worksheets.
The problem (and resolution) is described at: You receive a “Too many different cell formats” error message in Excel.
This provides a download for an add-in to automatically remove the custom formats: Remove Styles Add-in
and a couple of links with information on the style-copying problem, with a “hot-fix” download to fix it:
I have now run the Remove Styles add-in (once I found the new “Remove Styles” button on the Home tab), and it seems to work as advertised. I have yet to try the “hot-fix”.