Changing the Locale in WINE
I had to edit /etc/locale.gen
and un-comment these two lines:
ja_JP.EUC-JP EUC-JP
ja_JP.UTF-8 UTF-8
After that, I ran locale-gen
(as root), and when it finished generating locales simply setting LANG=ja_JP.utf8
worked. The key was generating locale information first, it seems.
Also, if you haven't got any, you'll need to install a japanese font on your system.
My distribution is Debian Sid, if anyone wonders, but I believe this is also what you need to do in Arch and Ubuntu and most other distros.
in Ubuntu 13.04 i had to use
LANG="ja_JP.UTF8" wine YourBinary.exe
LC_ALL="ja_JP"
another example to do it ;)