Epic's Rod Fergusson has acknowledged that "longer-than-ideal wait times" are being experienced by those in Gears of War 2's multiplayer matchmaking. He explains the issue is complicated and that there "isn't any one problem" causing the extended waits. The company is currently working with Microsoft to resolve the issue and hopes to have an update soon.
In the meantime, Fergusson has some helpful suggestions for those plagued with issues:
If you're stuck in a matchmaking loop where it keeps restarting, try a different list. It's a "possible population issue."
Issues seem to be "heightened" for parties of one and four. He recommends having a friend if you're flying solo.
Having a group of five pretty much alleviates all issues.
Or, if you're feeling obstinate that the system should work as intended, you can always pass the time with some reading material. We've been catching up on our 19th-century English literature. Vanity Fair is quite good.