Other language characters

I've been using Zen for many years now, but until recently my customers were primarily from US/Canada and a few from other English speaking nations.

Now, however, I get an increasing amount of traffic from Japan, Sweden, Finland and other countries that use non-English characters. When they pay using the PayPal Express Checkout, which then gets the address info from PayPal, I end up with garbage. For example, a customer provides (via PayPal):

〒488-0061 
愛知県 - Aichi 尾張旭市北原山町
六田池2112-1
Japan

And I get

å…##ç”°æ± 2112-1
尾張æ—##市北原山町, 488-0061
愛知県 - Aichi, Japan

As I've never dealt with language or character sets at all... can someone point me in the right direction for fixing this? Or is it even possible? Because obviously I don't want to set it to "Japanese" if that means English customers can't type their letters or Swedish can't type theirs... is there a "catch whatever they provide" set? And if there is, why isn't that always used?

• Steven