Try the same with shorter values. Really. MIME::Words is one of the ugliest hacks on CPAN (as is the underlying RFC). The encoded string should be at most 75 bytes long so you'll need to either split original (remember, Quoted-Printable multiplies the size in bytes by three and UTF-8 Japanese chars are more than one byte long) or employ MIME::Words::encode_mimewords (note plural) which will eat your spaces and do other interesting things.

Try to use the latest MIME-Tools package (dev version 6.0), it's more correct in this very place. Or import MIME/Words.pm from OpenWebMail which is almost perfect and has the same interface.

I'll be able to help you more if you show mail headers as they are on receiving side. I've invested days of blood and sweat in MIME encoding of mail headers once :)