Eu tive exatamente o mesmo problema. Estou usando o Puddletag para atualizar as tags id3, mas não parece que as alterações sejam refletidas na biblioteca do Banshee, mesmo depois de forçar uma "Rescan Music Library".
A única maneira que encontrei para fazer o Banshee atualizar as tags é removendo explicitamente os arquivos da biblioteca e adicionando-os novamente: clique com o botão direito do mouse em "Music" na barra de ferramentas à esquerda em "Libraries", selecione "Import Media to Library "e selecione a pasta onde estão os arquivos cuja tag id3 você atualizou.