Vou abrir um "p.s." em outra janela pra passar minhas impressões.
Instalei o Songbird; não foi um .deb mas achei bem fácil. Gostei muito do programa, da organização, das opções, das extensões e os skins. Em se tratando dos últimos itens é muito legal mesmo a possibilidade de instala-los como extensões típicas do Firefox. As extensões são muito bacanas e realmente melhoram muito a experiência. Infelizmente o programa é muito "pelado" sem elas, algumas, por ser um projeto novo, não funcionam bem sem usar métodos espartanos, outras nem com eles. O mais chato dele é não ficar na área de notificação e não mostrar a capa dos discos (sem extensão). Promete muito, gostei mais ainda dele por ser open source e universal, você pode usar no windows, mac, linux, kde, gnome...
No final das contas eu não sei qual usar, o Banshee é mais estável e maduro e tem quase tudo o que eu quero. O Songbird é um aplicativo promissor e eu penso em usá-lo para acompanhar o desenvolvimento, quem sabe reportar alguns bugs...