One of the features relevant to the system affected by locale settings is the text encoding, or the "charset", or the "codepage" – taken from the LC_CTYPE parameter. Although in many situations the text encoding is given by specification (e.g. D-Bus protocol strings are always UTF-8), there are also many places where the encoding is unspecified and has to be taken from the current system locale.
In particular, filenames are frequently shown according to the current locale text encoding. Programs written in Python 3, for example, use the current locale encoding if the program forgets to specify otherwise.
The 'C' locale implies 7-bit ASCII text encoding (ANSI_X3.4-1968), and part of your problem may be that while many programs (those written in C, generally) interpret this to allow arbitrary 8-bit values, there are also many programs which have a much stricter interpretation and reject any values above 127 (i.e. non-ASCII) as invalid. It might be that a decoding error is caused by some file name, or some configuration parameter, or some other text file.
In fact, at this point you'll even find programs which outright refuse to work with a locale that specifies the ASCII text encoding – some of them requiring UTF-8 specifically (such as gnome-terminal), and some others requiring any 8-bit encoding.
If your distribution applies the "C.UTF-8" patch to libc, use it:
If not, then use one of the following:
(You can run
locale charmap to see what codepage is in effect according to current environment variables – in both cases it should say UTF-8. If you choose the 3rd option, beware of buggy programs which directly look at $LANG instead of calling nl_langinfo(CODESET) as they ought to.)