Qualifier: I live in Tokyo.
All the large stores, especially the major electronics retailers and any international-level hotel, will accept most credit cards. American Express is certainly the least popular, if you can obtain a Visa you'd have very few problems.
Smaller stores, almost all restaurants under $50/plate (and some that are over), and the smaller non-chain hotels are cash only.
On the positive side, withdrawing cash from an ATM is much easier than only a few years ago. 7-11 convenience store ATMs accept Plus-network bank cards, so if it has the Plus logo on the back you just need to find a 7-11, and that won't be a problem.
Fees are $2 per transaction over whatever your bank charges, so don't go in for an extra $20. I usually withdraw Y50,000 - Y90,000 at a time.