Here's an article from the Microsoft KnowledgeBase that describes the
problem.
http://support.microsoft.com/default...b;en-us;213904

The error occurs when there are too many individual occurences of
individual formats. I like your idea about deleting columns, but that
may not relieve the problem if the entire row is formatted. For
instance: if you select row 5 and paint it yellow, it stays yellow even
if you delete rows.

This idea worked for me: I inserted a new tab in my worksheet, and
copied cell A1 (altho any cell would do). Because the tab was new the
cell was not formatted. I then pasted over the areas I wanted to
become format-neutral, which resolved my problem. It may work for you
as well if you paste over the columns that you mention.