'Too many cell formats' & 'Microsoft Excel cannot paste the data' errors, file corrupted?

When I try to change formatting in a spreadsheet A, I get the following message:
'too many cell formats'

When I try to copy data from spreadsheet B to spreadsheet A, I get the following error:
‘Microsoft Excel cannot paste the data’.

However, when I copy data from spreadsheet B into a new file it pastes fine. Therefore, I assume that spreadsheet A is corrupted? However it is the same file I use every single month and never have problems with it.

This is Excel 2010, 32 bit. Windows 7.

When I send these same files to another machine, I have the same errors. All of our computers are the same configuration.
Recreating the file is not an option, we need to repair the current workbook. Any help would be appreciated.

Thanks!