As a Canadian expat, my experience was nearly identical to FireBeyond's upon moving to the US. As you suggest, I was able to get a store credit card, then it was over a year (during which I never used the store card at all) before I was even considered for a regular credit card. If that's not symptomatic of a broken process, I'm not sure what is...
I honestly don't think it's broken. If I'm going to loan you money it makes sense that I'd like you to have a history of successfully managing debt and access to debt. You are more risky if you don't have a history.
It makes logical sense. Is it fair? I don't really think so, but its at least logical.
Yet other countries have no issue doing it differently.