Clementine not playing files with certain characters in the name

That's bizarre. "Ta fête" or "Ta fête", a UTF-8 locale system should be able to open them fine without problems. I just installed Clementine on a fresh copy of Ubuntu 13.10 and test audio files play fine no matter how I altered their pathnames.
I know this sounds stupid, but could you try checking your current locale by typing locale in the terminal? I doubt it's the problem but doesn't hurt to check.

Try locale -a and see if en_US.UTF-8 and en_GB.UTF-8 are available on your system. If they are, you'll want to open your locale configuration files by typing sudo gedit /etc/default/locale in terminal, and change everything to using en_US.UTF-8 (and LANG to en_GB.UTF-8 if you want UK English instead).

I think LANG alone should be fine, so your locale config file should look like this:

LANG = "en_GB.UTF-8"

After that, reboot your system and try play the files again.

Look at this for more information:
https://help.ubuntu.com/community/Locale#Changing_settings_permanently

If editing /etc/default/locale doesn't work:

First try to manually generate and reconfigure your current locale packages:

sudo locale-gen
sudo dpkg-reconfigure locales

Then nstall the language pack so as to make sure the locales do exist in the first place (just to be on the safe side):

sudo apt-get install language-pack-en-base

Then, open Language Support from System and try dragging English (United States) to the top, and apply it system-wide. Log off and back in, run locale in terminal to see if the changes apply. If it works, great. But it probably won't work if even manually editing the locale file fails, so try sudo gedit /etc/environment in terminal, and add this after PATH:

LANG="en_US.UTF-8"
LC_ALL="en_US.UTF-8"

Save and reboot to see if it takes effect. You should see locale giving you the correct output this time if it works, otherwise, your system is taking locale settings from some other location instead.

If it still fails to use UTF-8 for your system locale,

sudo gedit etc/bash.bashrc

Add in this to the last line (be careful not to edit anything else):

# Forcing locale to en_US.UTF-8
export LANG="en_US.UTF-8"
export LC_ALL="en_US.UTF-8"

Save and reboot.

As I tought, the problem is indeed caused by special characters in the file name or the path. Changing this will solves the problem.

A better solution would of course be to make clementine read the special characters correctly, but I haven't found out how to do this yet, maybe it's a bug.

edit: I might be this bug.

edit2: On second tought, I think it isn't, as Ubuntu uses UFT-8 (if I'm not mistaking, I have little knowledge about this stuff)