Selected Answer
You can't use the following characters in Excel tab names: / \ [ ] * ?
The list includes the colon which can be entered by some means but not by others and may be changed into a space by Excel.
In addition to these forbidden characters you must observe that a tab name can't be longer than 31 characters (presumably 15 for 2-byte Unicode characters), and you can't name a sheet "History" because Excel maintains a sheet by that name itself. (They don't let you see it, but it's there.)
I googled "can't rename excel tab" and found most people with that problem had downloaded the workbook from the Internet or received it by email. They complained about the loss of other normal Excel functionality. The consensus seems to be that the workbook is corrupt in some way. Nobody seems to have a resolution for the problem, but you may find hope or inspiration by looking for yourself.
You may try to copy the data from your workbook to a completely new one and hope that the error doesn't get copied along with the data.