Acho que encontrei!
Eu tenho notado o mesmo problema, embora eu tenha mudado para audacioso alguns meses atrás.
É um bug bastante interessante, então eu pensei que deveria procurar um pouco ...: -)
Eu corri exaile com '--debug' e descobri que o problema já é reportado como bug # 601235
(https://bugs.launchpad.net/exaile/+bug/601235)
Há uma correção confirmada no momento, mas ainda não foi lançada.
A solução do tipo "faça você mesmo" é bastante fácil. É dado no seguinte link:
Você deve apenas editar xldbus.py com seu editor favorito:
sudo gedit /usr/lib/exaile/xl/xldbus.py
e faça a linha 453:
tracks = trax.sort_tracks(['album', column], tracks,reverse=descending)
Salve, reinicie o exaile e pronto; -)