I am seeing complaints on Steam also about not being able to get a MP game. I wonder whether the attempt to stop steamrolling by largely separating teams from casual players is fragmenting the community and effectively providing a barrier to more casual players getting into the game. On Skirmish particularly the success of the recent pick up system means that the player base of regular players is largely invisible to casual players who are having long waits, which will eventually kill off the supply of new players (if there are long waits for a skirmish match players will give up trying).
I don't know what the answer is but I do know that we need to be encouraging new/casual players to enjoy the MP game.