I had a sort of hard disk catastrophe last night, and I was luckily able to recover most of my data, the directories most effected where my music directories. Now I have somewhere on the order of 10K mp3s but I don't know which ones where lost and not. It seems some directories have lost one song and others have lost everything. I have a complete playlist from before the incident and would like to check the playlist against the directory. The playlist is an .m3u type playlist that looks like this:

#EXTM3U
#EXTINF:0,311-11-Don't Stay Home.mp3
\\192.168.1.31\storage\250a\Music\311\311\311-11-Don't Stay Home.mp3

#EXTINF:0,311-15-Love Song.mp3
\\192.168.1.31\storage\250a\Music\311\Greatest Hits '93-'03\311-15-Love Song.mp3

#EXTINF:0,The Academy is-05-Everything We Had.mp3
\\192.168.1.31\storage\250a\Music\The Academy Is\Santi\The Academy is-05-Everything We Had.mp3

Now I am no Linux guru, but I know there must be a way to make a script that can parse this file and check the mp3s to see if they exist. Now I realize that simply verifying the existence of the file means little. Without a hash check there is no way to be sure that the files are not damaged, but I need some place to start.

The file server runs Ubuntu Linux and I can run the script there, so if there is some way to skip the \\192.168.1.31\ part of the file it would be handy.

I really need your help here guys,
Thanks.

Did you preserve the directory structure when you restored them?
Using the #EXTINF: lines you can just get the filenames:
Using the lines you mentioned you can include the directories:
Forward slashes may be better:
I think you may want to use the find command to create another list of the MP3s you managed to recover. Then use text tools to find similarities and differences.

For example:
To create a list of all of the mp3 files in the Music directory:
find ~/Music -type f -name "*.mp3" >mp3list

Suppose you saved a list from the first sed command as m3ulist:
cat m3ulist
311-11-Don't Stay Home.mp3
311-15-Love Song.mp3
The Academy is-05-Everything We Had.mp3

Now lets find items from the m3ulist that are in the mp3list:
grep -f m3ulist mp3list

If you sort the lists you can also use the diff or comm commands. Comm will print 3 columns. Uniq to file1; uniq to file2; common to both files. You can use either the -1, -2 or -3 option (or a combination) to turn off the respective column. So to list items missing from the m3u list:
comm -23 m3ulist mp3list
Remember that the lists need to be sorted.

Here is a little linux magic if they aren't:
comm -23 <(sort m3ulist) <(sort mp3list)

If you have a list of filenames, including the paths, you could use items in the list with the "file" command to analyze the file. If the first part of the file is corrupt, it may not be identified as an mp3 file. The file command examines the contents of the file. It does'nt rely on the filetype extension.

cat filelist | tr '\n' '\000' | xargs -0 -L 1000 file >mp3filecheck

The "tr" pipe & the corresponding "-0" xargs option are needed because of the spaces in the filenames. This won't guarantee that the file is OK, but if it is totally unplayable because the header info is whacked, that will probably show up.
Another way to do this if you have a short list is to redefine the IFS variable:

Wow what a prompt and exact response... Thank you so much. Quick question... how do you also get the sed command to drop the storage/250a/ from the list where all I have are lines like this:

Music/311/311/311-11-Don't Stay Home.mp3
Music/311/Greatest Hits '93-'03/311-15-Love Song.mp3
Music/The Academy Is/Santi/The Academy is-05-Everything We Had.mp3

I've played with that command and I have not been able to makes sense of it... it's magic I guess.
Thanks again, very helpful!