On the computer, a tag editing program (Tag&Rename recommended) can tag all the genres in your genre playlist in about three clicks and 15 seconds. Highly recommended.

When cleaning my tags, my empeg found bad-data tags that neither Winamp or Tag&Rename could find. Easily fixed by dropping the MP3 in Notepad and trimming the bad data off the end of the file. Do a windows search on *.mp3 looking inside the files for "Brava". MusicMatch Jukebox, I believe, put loads of bad data at the end of every file it encoded. That'll teach me to download MP3s off the Internet...

I've found my MP3s are quite resilient to hacking in Notepad, allowing me to trim off long silences at the end of songs, etc. You can kind of tell where the frame starts and ends, just select and delete.