Turn on the wide-character API calls for the program. Then use opendir/readdir to see exactly what the characters are, and use that in the source for the renaming.

If that still has problems (I seem to remember some places where using wide API's didn't actually handle the UCS-2 translation), use Win32::API to access the MoveFile Windows call directly. Also, use a system call to "dir" with the proper flags to get the short name aliases of the files in question, and then use =that= as the source name for the renaming. Hmm, I seem to recall cases where a short name wasn't generated if you had funny chars in the name but it was still short enough, so that might not work.