This exact same story pretty much happened to me when I moved to Canada about 15 years ago. I wasn't able to get a credit card for years, and couldn't rent an apartment without a guarantor, despite the fact that I was full-time employed in the tech industry, had zero debt, plenty of savings etc.
What I took from the experience (especially after going through various iterations of it in several other countries) is that most communities are biased against migrants/newcomers. Egalitarianism would be nice, but in practice nepotism and chauvinism are encoded in policy.