I would think that the command Edit>Find would work.
Keep your same worksheet names, just search and replace the old sheet name with the new one. Once you are sure that all the references to the old sheet are replaced, and all things on that sheet are no longer needed, then (if you want to) just delete the old sheet.
In the "Find and Replace" window, on the Find tab, just enter the name of the 'old sheet' and on the Replace tab enter 'new sheet' (or whatever you called it) in the "Replace with" field.
For the searching options select "Look in:" Formulas.
I believe that will work. I just tried it for cell addresses within formulas, and that worked, so I would think it should also work for sheet names.
I have an Excel workbook containing a number of "analysis" worksheets. These "analysis" worksheets extensively reference a "data" worksheet containing daily closing stock prices. Is there some way to replace the entire "data" worksheet in the workbook each day rather than manually changing all of the stock prices?
I've tried, but when I rename the old "data" worksheet, the formulas in the "analysis" worksheets change as well. When I add the new "data" worksheet, I can't figure out an easy way to get the formulas to reference the new worksheet. Any suggestions?

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic