The problem is that when you copy the files from one file system to another, the file names change. One file system might accept unicode of utf-8 filename, and the other might not, so it might convert it to codepage, or mangle the filenames in some way.
Unfortunately, the iTunes xml file doesn’t get mangled… it still has the “old” file names, so it can’t match up the “old” path to the “new” path.
That’s the root of the problem.
Really, the thing is that I don’t have a fix for it, really. Not for the ones with international characters. Clearly something isn’t right on the latest build, with not being able to find the files from the .xml file, but I’d have to have more details to be able to replicate that.
What kind of system was it coming from? What was the location of the .xml file, and where where the music files? What kind of file system was it on? When you moved it to your linux box, where did you put the music files? Where did you put the .xml file? And what type of file system is the destination system?