Japan for voice?
 

I'll be in Tokyo and the outer Okinawa Islands of Ishigaki, Iriomote, and Miyako in October. It sounds like buying a SIM for data in Japan is very expensive, especially since wifi is said to be really prevalent there, so I'd like to get a SIM for only voice. I have a quad-band GSM phone which I don't think will work, but my wife has a Google Nexus One which has 3G support. Should that work? Is one of the carriers best for this?

The Nexus One would flawlessly work on the whole Softbank network, which is UMTS2100. NTT DoCoMo however run their network with UMTS800, 1700 and 2100 of which the Nexus One does only support the latter. So with an NTT DoCoMo SIM you may have coverage issues, especially in rural areas, where it is likely that there's only coverage on the lower frequency bands (800 and 1700 MHz).

One issue you may have is the inability to buy prepaid service. The Japanese government has made it difficult for non-residents to buy prepaid service. If you are going there with the US military, you can usually buy prepaid service from an agent on base, but not in town. Prepaid calling is fairly expensive in Japan. I used to use an international prepaid SIM to make both local and international calls, as it was as cheap or cheaper than using a prepaid. For instance the current rates listed for TelnaMobile for incoming calls in Japan is ~US$0.18 and making local calls in Japan ~US$0.23. This comes very close to the total per minute cost of using a prepaid. I used to roam on both DoCoMo and SoftBank. Check their coverage maps to see who covers the outer Ryuku Islands. You may need to rent a PDC phone to get service out there.

According to media reports NTT have already shut down their PDC network in March. Now there's only their 3G network left.

However I've found this on the Japanese Wikipedia:which Google translates into:This proves my old theory, that UMTS850 phones (which are very common in the US) are fully compatible with UMTS800 networks, which came to my mind after I saw, that UMTS800 not only uses only frequencies from within the UMTS850-spectrum, but also UMTS800 channel numbers (UARFCN) are within the range of UMTS850 channel numbers:
UMTS frequency bands - Wikipedia, the free encyclopedia
So UMTS800 just seems to be a frequency-wise cropped version of UMTS850, allthough the designation of these standards (800 vs. 850) suggests, that UMTS800 operates at lower frequencies than UMTS850.

So if you own a UMTS850-compatible Nexus One, you could use most of NTT DoCoMo's network including the "FOMA Plus"-covered areas (FOMAプラスエリア). Note that there are two versions of the Nexus One, of which the first one would suit best for Japan:
for AT&T customers: UMTS 850/1900/2100
for T-Mobile customers: UMTS 900/AWS/2100

Wow! That was some changeover. There must have been 50M DoCoMo PDC handsets in operation. Also, I understood that the PDC spectrum was scattered in bits and chunks all over the place. It would seem difficult to get enough together with the right up-down offsets to accommodate WCDMA's glutenous spectrum requirements.

Afaik all PDC-phones sold in the past years were already UMTS-compatible, so only subscribers with very old handsets were affected by the shutdown.
I can't find any more specific information on frequency usage other than PDC used the following three frequency ranges:

• 800 MHz band: 940–956 MHz uplink / 810–826 MHz downlink (130MHz duplex spacing)
• 1500 MHz band I: 1147–1489 MHz uplink / 1429–1441 MHz downlink (48MHz duplex spacing)
• 1500 MHz band II: 1501–1513 MHz uplink / 1452–1465 MHz downlink (48MHz duplex spacing)

All these frequency blocks seem to have been refarmed and assigned to four LTE operators back in 2009 (Japanese gov't confirms frequency bands for LTE) allthough it seems like there hasn't been any LTE frequency band specified for the former PDC800-range (http://niviuk.free.fr/lte_band.php).