Hmm, the only other thing I would suggest is checking the character coding in Mozilla. Under the "View" menu there's a place where you can choose what coding to use; it's supposed to autodetect, but maybe it's choosing the wrong font (which would explain the square boxes). Also, look under Edit->Preferences, under Appearance, Fonts. Where it says "Fonts for: Western" you should be able to choose Japanese or other languages, and then select fonts appropriate for it.
Just out of curiosity, do other non-Western fonts work? Off the top of my head, try going to http://www.wikipedia.org/
and look at the portion towards the bottom that says "In Other languages"; there are several non-Western fonts used there.