There’s a new, much more comprehensive version of this post at http://www.lightroomqueen.com/lightroom-photos-missing-fix/
If Lightroom tells you that files are missing, before you start relinking, first check whether it’s only specific files, or whether the folder is missing too.
If the whole folder is missing and the folder name has turned grey, you can right-click on the folder and select Find Missing Folder. Point Lightroom to the new location, and it should update the links for all of the photos contained in that folder and its subfolders, as long as their names haven’t changed.
If a whole hierarchy of folders has gone missing, perhaps because the drive letter’s changed, you can relink just the parent folder, and it will cascade through all of the other missing files without further interaction. That’s why it’s useful to set your Folders panel up as a hierarchy before you run into problems. Alternatively, you could change the drive letter back to the letter Lightroom’s expecting.
If only specific files have been moved, click on the question mark icon, and a dialog will appear, showing the file’s last known location. Locate the missing file, and check the Find nearby missing photos checkbox shown in the dialog above in order to try to automatically relink other files in the same folder. Unfortunately if you’ve renamed the files outside of Lightroom, each file will need linking individually, although there are some possible workarounds.