Isso parece relacionado a um bug antigo que não é corrigido envolvendo uma certa versão do gstreamer
(0,10) usado pela Clementine - também vinculado aqui . (Eu vejo que ape
arquivos podem ser reproduzidos com o Exaile 4.0.0 beta, que usa o GStreamer 1.8.3.)
A solução mais simples é usar outro player de música (Audacious, Deadbeef, etc). A maioria dos players de áudio do Linux não é afetada por esse problema.
Se você precisar usar o Clementine, a conversão para outro formato (possivelmente sem perda) também faz sentido, pois ape
é um formato sem perdas. (Se você tem grandes coleções em formato ape com sub-pastas, você pode gostar esta resposta, onde eu sugiro substituir avconv
com ffmpeg
).