If really stuck you could try the Linux application Photorec - that does a good job of finding a wide range of files by doing a complete surface scan. Although it won't recover the files with their original names, for things like MP3s their are utilities that can rename the files using the ID tags in the files. It's also advisable to have it output its recovered files to another drive so you don't overwrite the original drive data in the process.
Useful live CD image and documentation here:
What actually happened to the drive that it requires data recovery?
If it simply got repartitioned then Testdisk on that same CD should be able to restore the previous partition table and file table making the files available again. (Presuming no thorough format was done of course).