Tuve que editar /etc/locale.gen y elimine el comentario de estas dos líneas:
ja_JP.EUC-JP EUC-JP
ja_JP.UTF-8 UTF-8
Después de eso, ejecuté locale-gen (como root), y cuando terminó de generar locales simplemente configurando LANG=ja_JP.utf8 trabajó. Al parecer, la clave fue generar información local primero.
Además, si no tiene ninguna, deberá instalar una fuente japonesa en su sistema.
Mi distribución es Debian Sid, si alguien se pregunta, pero creo que esto también es lo que debe hacer en Arch y Ubuntu y la mayoría de las otras distribuciones.
en Ubuntu 13.04 tuve que usar
LANG="ja_JP.UTF8" wine YourBinary.exe
LC_ALL="ja_JP"
otro ejemplo para hacerlo;)