In your MC library, you diligently rename your Maria Joao Pires songs to Maria Joćo Pires ( that's an 'a' with a tilda ), then sometime later you rename your files based on something that contains this accented character - all will end in an unhappy mess unless your storage device has a file system that can support this.
The character set that most Americans use is based on IBM437 ( sometimes referred to as CP437 ) - and this does not support some of the European accented characters. The European alternative is IBM850. Have a look at
http://en.wikipedia.org/wiki/Western_Latin_character_sets_(computing) to see the differences.
It turns out that Buffalo's TeraStation has a setting in the configuration menu that allows you to change from CP437 to CP850. However, after much discussion and protracted negotiations with Buffalo in Japan, this setting only affects the display, and not the underlying file system.
So, to cut a long story short, my Buffalo TeraStations TS-10TGL/R5 have been replaced free of charge with the New TS-H1.0TGL/R5 and all is now working as expected. And Maria's songs are correctly named on the NAS...