I wonder if you have to be certain to tag tunes with a genre tag rather than just the playlist that contains them.

I think that if you do a "search" on the player "by genre" it will only search for tunes with that tag, not for playlists.

I could be wrong.

Anyway, the way to make sure is to multiple-select all the tunes in that playlist and change the genre of the tune instead of the playlist.