This has happened to me and at least one other person.
Since the patch, I did the level 40 story and got the key. I don’t consider this to be “early” in the story, so assumed I could still get the level 10 key on a new character.
So a day or 2 ago I started a new character and did NOT receive the level 10 key.
Others on the forum have claimed they got the level 40 key after getting the level 10 key since the patch, but apparently you dont get it on a new character after getting the level 40 key on an older character.