Think problem is more that missions do not work for all players, at least not reliably enough do you can make it a requirement for all new players.
I think "Newbie Room" should be more than just normal room with elo limit:
1) Limit it to one map.
It is players first game, you want to make sure it is on a decent map.
That map should be a very basic one, so no water map or any "complicated" terrain.
Could even make a special "newbie map" with hints/signs on the map like "good position to build defense." That takes some work to make but not as much as a full tutorial.
Also prevents the "tons of map dls are starting because map is changed so often" problem.
1b) SC2 has beginner maps where rushing is harder, because the entrance to base is blocked with stones. Could do something similiar.
2) The newbie room games should not effet elo. Elo is supposed to meaure skill but if two very new players play each other it is more luck than anything. Instead have an archivement for winning a match on newbie host. 5 wins are required to play on normal host.
Sure, that can be cheated but so can elo. And even killing NullAI 5 times is more experience than some players have.
3) Limited unlocks for obvious reason.
Imo could even change the unlock system: On newbie host it is limited, in others rooms everything is buildable.
4) Not sure if/how that is doable: When player has wanted ~5 minutes in battleroom and no opponent joined, ask him if wants to add a bot player.
5) Whatever requirement is added, require it for existing good players too.
So that you have experienced players testing the system and reporting problems.
(new players are unlikely to report problems, they just leave)