If the links were originally to files in the same folder as the
spreadsheet (or possibly sub-folders thereof) then Excel will hold them
as relative links by default. So, when the spreadsheet gets moved
somewhere else the links will be interpreted as relative to that new
folder and the files may well not reside there.

I recommend trying the following (2003 or earlier):
File Properties Summary Hyperlink Base:
\\SomeNonServer\SomeNonFolder

In Excel 2007 you get there by [that's progress for you!]:
Office Button Prepare Properties Document Properties Advanced
Properties Summary

This will force Excel to hold hyperlinks as absolute rather than
relative to its assumed base (the folder it came from). Then remake
any links which are not pointing to the right place.

If you try this, please post back here with the results so that others
can tell whether the advice is worth following or not.

Bill Manville
MVP - Microsoft Excel, Oxford, England
No email replies please - respond to newsgroup