The safest way would be to move the files back, and then move it with MC. If that is not doable or if it's time consuming, try this (as always, do a library backup first!):
Select the missing files, right click, library tools, and then hit "Find and Replace". Copy the previous folder location like: "d:\Videos". You can find this in the tag data on the files in MC. Find the new folder path, like: "e:\Storage\Videos". You'll now have to enter the first path in "Find what" field, and the new folder location in the "Replace" text field. Mark all necessary library fields. If not sure, then mark them all.
This normally moves the files on the disk as well, but as they are already moved, only the meta data paths should be changed I think.
*Edit*
As Alex says, you'll need to add the new folders to the auto import to fix things later on.