I just got back from Japan. I took a Motorola c975 phone purchased from 3 in the UK. They can be bought unlocked off e-bay for about US$100. The phone is triband GSM plus 2100mhz WCDMA. The phone worked perfectly in Japan using SIMs from various providers. (I've loaned this phone to friends travelling to Japan as well).
If I didn't have this phone, I could rent an unlocked 3g phone from various rental boths at Narita. It costs roughly US$6 a day. They will provide you with a SIM that effectively functions as a prepaid SIM, but they want it back when you are done. Here is a link to DoComo's booth at the Narita:
http://roaming.nttdocomo.co.jp/service/detail.htmlBefore this option, I rented phones from
http://www.jcrcorp.com/ and was happy with their service. I took advantage of their free incoming calls and used a callback service to reduce the per minute rate on outgoing calls.
Contrary to some things that have been written, a GSM SIM functions fine in a 3g phone. I've used SIMs from the US, UK, HK, NL, UAE, and FL in the phone without incident. DoCoMo rents the Motorola c835 to travellers which is similar to the phone I am recommending. It is also similar to the Vodafone 702s sold by Vodafone.
I highly recommend the c975 as a traveler's phone. It is not the cutest phone out there, but it is rock solid and covers most bands out there. The only band it doesn't have is GSM 850mhz for Latin America. While the GSM situation is changing down there, I still find that an old ATT TDMA (e.g. a Nokia 6160 or 6360) bought off e-bay for $25 is the best solution for those countries.
Incidentally, for more stuff on international roaming checkout prepaidgsm.net. I'm a contributor to the website and we have a lot of info on getting going in various countries.
With respect to prepaid in Japan, DoCoMo has discontinued it. Vodaphone still has it, but they are requiring all owners to register their phones. You are not likely to get one unless you know someone in the US army stationed there. They are still sold at the PXs on base last I heard.
Stu