This is the way I would have recommended you that you go about it. If your library is in a non-standard layout then normally it still works as long as the media is restored to the same paths it held previously. Click a broken file and click CTRL+I to Get Info, then locate the file when prompted. iTunes may then offer to try to locate the rest of the missing files. This is sometimes successful. Otherwise I have a script called FindTracks that should be able to do the trick.