This plugin will let you pick a new folder. It will search that entire folder (recursively, all the sub-folders) for the textures, and do that for every missing texture. It will search for color texture, bump, transparency, and bump files. When you save the file, all the new paths will be changed to found location.
To use the attached plugin do the following:
Email comments to Max Fugier.