When I am looking for game, it will find all players at relatively decent speed but it will almost always get hung trying to find the last one. This can take in upwards of 3-5 minutes if it finds anyone at all. Usually people quit at this point and the cycle continues.
Yes this happens to me as well. It actually will find more people eventually, even if people leave.