To verify, have you removed any protect worksheet as well? Also, does the
workbook happen to have a macro, or any VBA code in it? Right-Click on the
tab name and select View Code. Not sure if you'd have any code there locking
the tabs...
If nothing else works, and you have no programming in the background, you
can always move all other sheets to a new workbook and overwrite this one.
May not fix, but it sure does work...