I know this is a very old question, but do verify that your download of File Name Encoding Repair Utility is version 1.1 from May 26, 2006. It is linked (and is listed as v1.0) at https://support.apple.com/kb/DL355?locale=en_US.
Apparently, this software was updated to be Intel compatible in 2006 with no fanfare.
I downloaded this utility in 2017, ran on MacOS Sierra 10.12.2 on a MacBook Pro, and ran it against a few folders with garbled Japanese text from Mac OS 9. It corrected the file names as expected.
I was then able to shift the text encoding of the files to Japanese using SUE in Mac OS 9. There's some differences with Shift-JIS in Mac OS X that I was unable to translate 100% of file encodings using just TextWrangler. Perhaps running SUE in SheepShaver or another Mac OS 9-era emulator may assist.
Using the File Name Encoding Repair, SUE, and Google Translate, I was able to get some old software working. This should help if anyone else finds this in the future.
recode
andiconv
(from <stackoverflow.com/questions/691040/…). The difficult part will be to guess the original encoding...