I've had success using the the Jcode module when dealing with Japanese characters.

Or if you're using Perl 5.8 already, you can take advantage of its Unicode support.

Good luck,
Staunch