How to mass replace old dead links with new links in a Wordpress blog?

[mahjong]

so the filenames are the same? And the host is the same too?

Because if you have a http://filesonic.com/sdijohfsdjkf/BLABLA.avi
and the new would be http://www.filesonic.com/aasdahfsdjkf/BLABLA.avi
then you can replace it with regex. At least the filenames should be the same for this to work with a mass number of urls.