What appears to be the main issue is that the filenames are in fact NOT using the correct unicode characters. The cedilla for instance was made up of two characters in the problem names.
Ah! Good spot. There are two (common) ways of writing accented characters in Unicode, "NFC" (normal form composed), where you use (say) a c-cedilla character, and "NFD" (normal form decomposed), where you use the normal c character followed by a "composing cedilla". The MacOS API is defined to use UTF-8 NFD, Linux (and probably Slimserver) use UTF-8 NFC, and Windows and thus NTFS use UTF-16 NFC. It looks like something along the way has managed the UTF-8/UTF-16 conversion but botched the NFC/NFD conversion.
Googling all this produces
http://macntfs-3g.blogspot.com/2009/02/ntfs-3g-200921-update-1.html (last comment).
Peter