That's strange. Both countries present challenges for those with US-issued ATM cards, but those problems are usually solvable. In China, your sure bet seems to be the Bank of China (worked every time for me!), although I had about a 20% success rate at other banks displaying the Visa and Mastercard logos. In Japan (and my memory is now a few months old) Citibank and the post offices worked great.

The surprise in Japan is that acceptance of US-cards isn't more widespread: still, with a little planning, I had no real difficulties. I recall being in Himeji and having to ask the tourist office for assistance: they already had directions written up, so it was obviously a common question (the ATM was an ancient post-office affiliated machine in the bowels of the station -- all the modern machines in the fancy banks on the main drag didn't take US-issued cards). Next time, I'd recommend asking the tourist office for help.

Of course, there could have been something strange with your companion's card. But if it was on the Mastercard or Visa network, it should have been possible to get cash somewhere in Japan.