Comment 7 for bug 1196059

I had this problem, and also had another problem related with the use of UTF-8 in my filesystem. I didn't think there was a link between both, but solving the second problem solved the first.
My system was not using UTF-8 even if my etc/defaul/locale said so.

My problem is described here and the solution to it is nicely explained there as well.
http://askubuntu.com/questions/426650/clementine-not-playing-certain-files/431630?noredirect=1#comment560786_431630