I have an external HD formatted for FAT32 so I can use it between my mac and PC. Now, I also installed linux on my pc and when I was running that, it detected my external, but then I re-booted in Windows and half the stuff on it became corrupt. It still says that my external is filled... but now I can only access some of it. Is there a way I can recover it or do I have to re-download what I had (It was a majority of my music).

I know that there are some good recovery tools for linux, but I've never had to use them.

Hopefully someone else here can help you a little more, but if not, here's a place to start looking.
Good luck and if you do make any progress, please post some updates. It may come in handy later on.
-mm

Win program called GetDataBack actually worked very well for me.

GetDataBack is KING of getting data back... hmm I guess the name fits.
GetDataBack also comes in two different flavors. one for Fat32 one for NTFS, make sure you get Fat32 if that is how your drive is formatted.
And make sure you have a place to put the files when you are recovering... you'll need enough space for all of the files you want on a different drive.