I'm not exactly clear on what the problem is but, fwiw, the usual way to
change links is via Edit, Links, Change Source.

I'm guessing that you used Insert|Hyperlink to create the hyperlink.

Then you changed the value in the cell (the stuff you can see), but you didn't
change the address of the hyperlink via insert|hyperlink.

David McRitchie has some code that you can use to change the hyperlinks:

http://www.mvps.org/dmcritchie/excel/buildtoc.htm
look for:
Fix Hyperlinks       (#FixHyperlinks)

If you're new to macros, you may want to read David McRitchie's intro at:
http://www.mvps.org/dmcritchie/excel/getstarted.htm

====
You may want to start using the =hyperlink() worksheet formula.  Then you'll be
able to do simple Edit|Replaces to point at a new location.

=HYPERLINK("C:\My Documents\Excel\book2.xls#sheet1!c99","click me")
could be changed to:
=HYPERLINK("C:\My Documents\Excel\book2.xls#sheet2!c99","click me")
or if you need apostrophes surrounding the worksheet name:
=HYPERLINK("C:\My Documents\Excel\book2.xls#'sheet 2'!c99","click me")