I don't think that it has too much to do with what country you are from because in some cases they don't know if you sign up for a card by mail or through a store. My suggestion is to first try to get one through Costco Japan. I got my first Master Card from there my fourth year here, no problem. I tried for the heck of it at one store (can't remember which), but got turned down. What really ticked me off was that my own bank, Mitsubishi Tokyo which I have been with for 7 years, turned me down!!! (I had trouble with them before because I think they were doing one of those police checks of gaijin cards because they claimed that my hanko did not match the hanko stamp on file, even though I got it hand-made from China, totally uncopiable! They asked to see the card, after that, no problem with the hanko!) I also just got one from Citibank Japan, no problem, but I have to pay an annual fee if I don't keep a certain amount of money in the bank.

The problem here is that the system is VERY subjective, even for Japanese, and there is no system of "building credit" here, like in the US per se. If you can, do it through a store but if ANYONE asks you to see your gaijin card, don't bother. And remember, actually the law says that you only have to show your gaijin card to the police and immigration (The problem is that some places actually DO need some sort of proof of residence, even from Japanese; but I have a Japanese drivers license like most Japanese do, so this is no problem for me.)