I'm using Linux (2.4,10ish, Blackdown J2SE 1.3.1).

All accented characters are affected - one example is for the playlist "N��àdurra" (that's a-grave after the N).

LC_ALL=en_GB

I don't think it's merely a font issue, as writing back to the player didn't preserve the characters. Do you use the default String/byte converters anywhere (e.g. new String(byte[]) or String.getBytes() without specifying an encoding - or equivalently, new StreamReader(InputStream) or new StreamWriter(OutputStream)?