Getting back to my comment above about contacting the Comptroller of Currency, I went to their site and could not find anything very specific.
However, I do believe that a regulated lender may not arbitrarily refuse you credit merely because your credit references are not on their everyday list of sources. If you make a good faith request for credit and can supply evidence of a favorable credit history, I believe a credit card company would be in violation of fair credit regulations if they refused to take that into account.
Write to : Comptroller of the Currency, Washington, DC 20219
or online,
www.occ.treas.gov and look for an applicable feedback form.
Have you tried applying for a Discover Card? They have been very aggressive about expanding their credibility in the marketplace, and I bet they would pay attention to your arguments. Also, American Express is a more internationalzed organization, and are probably better equipped to access and explore your credit history in Canada.