No repositório, há várias ferramentas para alterar tag's de arquivos MP3. Uma delas é a tagtool (que, depois de instalada, fica com o nome Ferramenta para Etiquetar Áudio no menu Multimídia.
Tem também um player, o Quod Libet, que é muito bom tanto como player quanto para administrar as tag's.
No entanto, às vezes o arquivo MP3 pode estar com problemas e a parte que contém a tag não registra as alterações feitas. Também pode acontecer de o arquivo ter a tag no formato id3v1 e não o formato mais novo, o id3v2. Me parece que no formato id3v1, você não pode colocar qualquer gênero que quiser mas apenas um dos que constam em uma tabela padronizada. Aí, quando você altera e coloca um gênero não padronizado, ele não é registrado no arquivo.
Já no v2, entre outras facilidades, os campos podem registrar valores mais extensos (título da música, p.ex.) e pode-se colocar qualquer gênero que se quiser, não se ficando obrigado a escolher um dos padronizados.
Algumas ferramentas (e alguns players) não conseguem criar tag's no formato id3v2 se os arquivos já não tiverem esse formato. Outras ferramentas criam este formato se o arquivo só tiver o id3v1. Não sei em qual das duas situações se enquadra o Rhythmbox.
Um abraço.