I have the exact same problem with Quantum of Solace. I think it has something to do with the backup loader, since I also have problems with SSBB(It doesn't find players until about the 3rd time I connect to NWC. Once it finds them, though, its rock solid.). I'm hesitant to say that, however, because Mario Kart works perfectly, almost instantaneously, for me.