I lived 3 years in Japan and did not ever have a problem using a US issued Capital One Visa credit card. Scratch that... once at a gas station. An Idemitsu near NRT airport.
They are certainly not ubiquitous but my preference was to use Citibank for ATM.