He's unlocked in some of my menus and locked in others.
I do NOT meet the requirements to unlock him, frankly I'm quite away from earning him.
He is absent from the character select screens with their pictures displayed (Lobby and Multiplayer menu).
He is selectable while in matches, so after a match starts -> I push "Start" -> "Options" -> "Multiplayer" and now he is selectable there.
I don't know how long this has been happening as last night it was the first time I ever switched my character this way. Joined a game and EVERYONE on my team was the Queen, so wanted to switch.