MusicBrainz Tagger (Score 5, Interesting)

An amazing program that allows you to not only modify the ID3 tags of your mp3s, and rename them accordingly, but does so automatically, by creating an acoustic fingerprint (TRM) of the song, and comparing that to other TRM's from its online database. The more people use it, the better it gets, as there are more TRM's to compare your own against.

From the description on its homepage:

The MusicBrainz Tagger application allows you to automatically look up the tracks in your music collection and then write clean metadata tags (ID3 tags or Vorbis comment fields) to your files. As you tag the files in your collection that MusicBrainz didn't recognize, you submit the acoustic fingerprints (TRM ids) of your files back to the server. Submitting acoustic fingerprints will allow MusicBrainz to automatically identify these tracks in the future, so that other people using the Tagger can benefit from the work you have done.

Don't let that discourage you, though. The program is fully usable right now.
From the Statistics page:
Artists 155884
Albums 261790
Disc IDs 124538
Tracks 3211514

It's a gem.

For now there's only a Windows version out, but the program is GPL'd, and the source code is available to everyone.

Download it here:
http://www.musicbrainz.org/tagger/download.html