14.04 e posterior
Eu verifiquei as dependências da clementine e posso confirmar que são necessários os plugins gstreamer 0.10 e desde wma O suporte é fornecido pelo plug-in ffmpeg necessário para configurar o seguinte PPA para ativar o suporte a WMA para 14.04 e posterior:
sudo add-apt-repository ppa:mc3man/gstffmpeg-keep
sudo apt-get update
sudo apt-get install gstreamer0.10-ffmpeg