Exactly, it would need several years maybe decades for MS to be as well known as Playstation or even Nintendo here.
Nobody denies that there is brand loyalty due to historic reasons.
But If you only look at this through the xy-land glasses you won't see the differences that eventually lead to a stronger brand loyalty. There was also a time when people called consoles "A Nintendo". Sony changed that pretty fast. Not only because they had the better console. Sony had big offices in all countries back then and they managed cater to the small cultural differences and treat all markets well.
For instance:
-In germany most 360 exclusive were not released (which wasn't MS' fault) or released for PC too. While the 360 definitly had great exclusives in the first years - that was not the case for the german gamer
-Portugal is a small market. It has only 2 million more inhabitants than NY. While MS didn't even bother with translating their OS - Sony did full voice overs for games like Uncharted
-Sony has been advertising in CL and also FIFA Events for years
-XBL wasn't available in a lot of smaller countries or came really late
-Sony has a lot of european studios
The way how MS handled the EU launch was ridiculous but exemplary. Tier 2 countries. Or that they still force you to use game language of your marketplace. Irish aren't allowed to use Kinect voice recognition if they don't move virtually to the UK. In Austria you can't use german for Kinect because Austria has no voice support. Not even english. And so on.
If they would have handled it different, it wouldn't have turned the tide instantly. But you have to show good will to gain brand loyalty - it takes some time. MS is still completly ignoring europe. This whole language-marketplace thing has no point at all and everyone hates it. But they are still going like "Huh we have different languages in US, who cares about There-be-Dragons-Land?". It wouldn't even take a big effort to change this.
360 did well in europe, even if it was beaten by the PS3. It could have sold a lot better, if they had put a bigger focus on the different EU countries.
"They can never win europa because it's Playstation Land!" isn't an attidude that helps.