Você pode remover seu banco de dados para forçar banshee
a criar um novo.
O arquivo de banco de dados está localizado em ~/.config/banshee-1
e seu chamado banshee.db
.
Saia do banshee (certifique-se de que esteja realmente fechado)
Criado um backup do banco de dados chamado banshee_bak.db
mv ~/.config/banshee-1/banshee.db ~/.config/banshee-1/banshee_bak.db
Abra o banshee novamente e re-indexe sua mídia.