I don't know squat about anything newer than excel 2003 and Windows XP.
However the error message you describe vaguely resembles the error message I get when I have data inadvertantly added to the last row/column of the spreadsheet and try to add a row. The solution is to delete the errant data, put the cursor into cell A1, and save.
That's a logical problem for adding, not so much for deleting... might be completely in left field.
Of course based on the error message, you might want to retry it with all other applications and spreadsheets closed.
=====================================
Eng-tips forums: The best place on the web for engineering discussions.