A bunch of co-workers have purchased the Garmin Nuvi 360. To have the Japan map, you must purchase it in Japan (you're going to want to sell it to someone else in Japan before you go back home, too--either you can't get US maps to load into it, or it is cost-prohibitive).
I just bought mine TODAY at Yodobashi in Tokyo for 52800 yen (approx $493). It is in Japanese, but there is a way to change the output language (speach, user input for saved data points, etc.) to English.
If you want to go to a certain address, you will need to know it in Japanese. But, you can go to a phone # (been told this will get you within a block or so), or you can go to a lat/long coordinate that you pull off of something like google-earth (extremely accurate directions).