Isso parece um bug no clementine
ou pelo menos na versão que vem no pacote do Ubuntu. Eu uso isso no meu Debian e não vi isso antes, mas eu o instalei hoje em uma VM rodando o Ubuntu e ele apareceu em francês. Eu moro na França, mas não tenho absolutamente nada definido para francês no meu sistema, muito menos a VM.
Então, parece que Clementine está assumindo a linguagem com base em seu IP ou algum outro método tolo. A boa notícia é que há uma configuração para isso, pelo menos na versão 1.1.1, que é o que está nos repositórios 13.10.
Basta acessar "Ferramentas" = > "Preferências" = > "Comportamento" e altere o idioma: