I have tried the PvP queue, and find it very lacking. There are too many options that require too many players. It takes about 30 minutes of waiting to actually get into a game, and that's only if it's a game that's popular with enough other players.
I suggest a priority queue system. Basically, when you enter the queue, you will 'rate' each of the options on a scale from 0 to 5. Like setting space to 5, ground to 3, fed vs klingon to 5, fed vs fed to 0, and what ever else options that are wanted. Then the system goes through each of the game types, pulling in people that have a 5 in them, once all the 5s have been placed into queues, it pulls in the 4s and so on and so forth, weighting each member by their position in the queue (in other words, making sure that people aren't stuck waiting just because their preferred gametype isn't high on anyone else's list), until there are enough people in the games to start them. This way, you might not get into your 5, but at least you will get into a game type that you can enjoy quicker, rather than having to wait for enough people to enter the queue for the one specific gametype you want to play. I suggest having a display that shows an aggregate of everyone's priority lists, and perhaps allowing people to change their priorities. Think of it as everyone in the queue voting for which gametype they want.
I would like to see a queue system like Champions Online. Rarely did you have unbalanced 5v5 teams.
Somehow, they worked it to where all people who chose "accept" would end up in one of two rooms, to where they would wait to enter the arena until both groups had 5 members. At that time, the door would signal that you could enter the arena. It appeared that invites continued to go out and the first 5 that "accepted" would join the battle, and the remaining in the queue would be sent invites for the next instanced arena, etc. However, I don't remember if it supported "premade" groups or not. I will say that rarely I had to wait more than a couple minutes between matches. You spent 90% of your time in the arena, rather than waiting in a queue.
Something simillar could be done with an area for each side with a "gate", that you could not click until all 5 people arrived on both sides, then when you clicked it, you would enter the arena space.