Excel error - too many different cell formats

Most of the solutions on the web aren't helpful

excelforum
groups.google
"including the possiblity that if you delete a format of a cell it
really does not go away"

Removing all formatting won't help you and support.microsoft tells you nothing

The issue is that this error is actually misleading, it's not the cell formats but the styles that are too many. What you need to do is this

Delete styles collection

The code for the macro is duplicated here for posterity

Option Explicit

'Deletes All Styles (Except Normal) From Active Workbook
Sub ClearStyles()
Dim i&, Cell As Range, RangeOfStyles As Range
Application.ScreenUpdating = False
Application.EnableEvents = False
'Add a temporary sheet
Sheets.Add before:=Sheets(1)
'List all the styles
For i = 1 To ActiveWorkbook.Styles.Count
[a65536].End(xlUp).Offset(1, 0) = ActiveWorkbook. _
Styles(i).Name
Next
Set RangeOfStyles = Range(Columns(1).Rows(2), _
Columns(1).Rows(65536).End(xlUp))
For Each Cell In RangeOfStyles
If Not Cell.Text Like "Normal" Then
On Error Resume Next
ActiveWorkbook.Styles(Cell.Text).Delete
ActiveWorkbook.Styles(Cell.NumberFormat).Delete
End If
Next Cell
'delete the temp sheet
Application.DisplayAlerts = False
ActiveSheet.Delete
End Sub

Of course, you'll need to format your whole Workbook again but you don't lose any data.
For those working with 2007 xlsx, I would not recommend the macro-enabled xlsm.
This VB code hangs for xlsm but works fine for xls.