I didn't know that it works when the workbooks are open together. Good to know.
The way I've done it in the past (though think prasaddn's approach above is better), is to use 'find and replace'. You can get to this with ctrl+F, and then click the "Replace" tab. Insert the name of the old worksheet in the 'Find what' box and the name of the new worksheet in the 'Replace with' box. Then, choose "Options" and select to look within the workbook instead of just the sheet (that way every link gets updated, not just your current sheet's links).
Sometimes, when your worksheet names are also cell values, you can accidentally replace something that was correct and didn't need changing (in addition to the sheet names). A way to avoid doing this is to do the above steps, and before confirming, choose to "Find All". Then, you can sort the various columns of information returned to make sure that you're only replacing sheet references. After that, then you can confirm.
