Tente testar outro media player baseado no gstreamer (ou seja, Totem, Rhythmbox), e se eles não funcionarem (para os mesmos arquivos que você tentou tocar com o Banshee), então você tem uma instalação do GStreamer quebrada.
Ao executar o Banshee a partir do terminal, depois que eu clico em uma música, um pequeno x aparece ao lado do título da música e eu recebo esta saída:
GStreamer-CRITICAL **: gst_element_query: assertion 'GST_IS_ELEMENT (element)' failed
Como o Banshee começa, eu também recebo essa saída (pode não estar relacionado, não tenho ideia):
[Warn 17:57:43.999] Failed to start DAAP client - System.Exception: No Zeroconf providers could be found or initialized. Necessary daemon may not be running. (in 'Mono.Zeroconf')
Eu tentei atualizar o gstreamer, mas isso não ajudou. Atualmente estou usando o Gnome3. Alguém sabe o que está acontecendo?
Tente testar outro media player baseado no gstreamer (ou seja, Totem, Rhythmbox), e se eles não funcionarem (para os mesmos arquivos que você tentou tocar com o Banshee), então você tem uma instalação do GStreamer quebrada.
Tags arch-linux