I have not had much problem with this. Acording to the MS Kb this is related to workbooks created in an earlier version. I've seen a lot of problems with the Excel 97 'Too many Cell Formats' Error that was making us crazy. I think the place to start is by simplifying your workbooks where possible.
Delete empty worksheet
Remove refrences and orphan refrences.
Remove links to other workbooks.
to check for refrences use:
This will give you a list of defined refrences in the workbook.