im pretty much in the same boat - all my friends can play each other, but i can't play any of them. I posted it, and i got answers which pretty much said my internet was slow (which it isn't) or that i should change my NAT to type 1 or "open". im yet to do it, but to do it, find you "default gateway" through network settings or cmd (command prompt). I use cmd, so to find it, type in "ipconfig /all" (without ""). A whole bunch of numbers should pop up - look for DEFAULT GATEWAY. just put that number into your internet explorer or firefox browser,...
It should come up with all your router settings.....
i have a belikin router, so i just click NAT but its prob diff with other routers.
From what i've seen on youtube and whatnot, you need to have both the UPNP and the NAT encoding thingy enabled.....
Not too sure if this works - yet to try this. Maybe you should look around for other ways on getting your nat open before taking my word.