how do I get the output from readdir to be correct -- NOTE: the filenames returned by readdir aren't usable (i.e. testing them with "-f" or such returns "no such file"....)...

readdir returns bytestrings, are you giving -f unicode strings or byte strings ? See perlunicode about that.

If you're on win32 see Win32::Unicode, Win32::Unicode::Native, Re^5: Is File::Find Unicode-(Conformant|Compliant|Enabled|Capable)?