I downloaded a bunch of chinese mp3s, but a large number of them does not display correctly. I can rename the files one by one, (using this
http://www.mandarintools.com/email.html) but I would like to have an easy way to do a large number of files at once. Does anyone have experience with that? I am using Win XP.

Is Chinese set as your OS' non-unicode language? I had that problem with Korean software and files, and once I changed the non-unicode language to Korean, everything displayed correctly. You can change it in Regional and Language Options or whatever it is (I have Windows Vista so I don't remember how to do it in XP anymore).

Nope, that did not help. My music-player still shows messed up fonts - and on top of that the programs that use ö,ä,ü etc (German charachters) are messed up.

For general file renaming you can find several options at Lifehacker.

Specifically for renaming and editing mp3 file tags, you can find Tagscanner, also at Lifehacker.

Take a look at the guide below; it explains how to use mp3tag, which you can use to retag it (windows only though, so you might need to use WINE if you're a Linux person ).

Here's the link to mp3tag:
http://www.mp3tag.de/en/download.html

Here's the link to the wonderful guide that explained how to do it:
http://www.nixer.org/encoding-id3-tags-mp3

I'd been looking for WEEKS for a way to do this, and had been struggling with garbled songnames. No way I was going to manually rename 3000 songs...

For the record, I also tried EasyTag, but couldn't get it to work. A guide to this sort of thing on different systems could usefully be stickied here? Seems like a common problem for Asian languages.

I feel a little bad, because I tried to do this some time before and got some pretty good answers here:
http://www.chinese-forums.com/showthread.php?t=27829
However at that time I was not able go through the steps. I tried again some days ago and it worked fine.
Anyhow, thanks for the answers.

Musicbrainz is great, if all of your music has been input into the database already..

Mp3tag also what I've been using when I dl an album and the encoding is messed up. I second it's suggestion