The old way I used to change genres in iTunes was to arrange the main window by genre, select all of a given genre, press Command-I to open the Info window, and then enter the new genre in the correct field.
Here's a better way: from the View menu, select Show Browser, which puts a three-paned window atop your library. Then, simply select the genre (or artist or album) you want to change in the browser section, press Command-I, and change what you'd like. Everything changes at once.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20060919113051206