Hi all. Sep was kind enough to post the original question for me. Since I have solved the problem, I thought it only right to follow up with you guys and pass on what worked for me.
Just for clarity, I have 2 Xbox 360's on my home network. I can run either one just fine but once I turn on the second one, it fails to find games I can play (MW2, for instance) even though it successfully logs into Live!
I was using a Linksys WRT54G router.
I researched this issue thoroughly but the only solution was always to forward 4 ports to my Xbox (53,80,88, and 3074). Well obviously you can only forward ports to 1 box, so that just won't work. I did try turning on Port Triggering but that didn't work either.
I tried setting up a DMZ. I changed the Xboxes to fixed IP address instead of DHCP and I added 1 box to the DMZ. DMZ, by definition, does no port filtering so port forwarding will not be required. I then set up port forwarding for the other Xbox (the one not in my DMZ). My WRT54G router does not allow more than than 1 device in the DMZ, so putting them both there was not an option.
No joy.
One tech guy I know suggested that I need to enable uPnP on my router and that the 360's would be able to configure the router to their own needs. I told him it was enabled and he suggested I get a new router (since the 54G is a bit dated). I bought a Linksys WRT160N router. I had also read that MS recommends routers that carry the "Compatible with Windows 7" logo for compliance with the 360's. This met that standard.
Simply turning on uPnP did nothing for my problem. I then ran through all of the port forwarding / port triggering / DMZ attempts I had made earlier. Nothing.
I spent 4 hours on the phone with Xbox tech support. The only solution they could give me was to forward my ports to the xbox. When I explained that this was not a solution since the problem involved 2 360's, they hung up on me. I was being stubborn and called back. In total, they hung up on me 4 times. I never raised my voice or was rude but I refused to accept that simple port forwarding was the problem.
Anyway, I was about out of options when I stopped in at my local Gamestop. One of the guys at my local store is a real geek and knows his stuff. I asked him if he knew of any slick solutions. He said "Yup"!!
He recommended that I buy a Netgear router. That's it. He said he had the problem and that when they tried a Netgear router, it went away. He knew of a few other folks that did this to solve the problem as well.
Ok, I was willing to try anything. I bought the Netgear WNR3500 router (wireless N router). I plugged it in, did a basic setup on the router, made sure uPnP was set up and tried it. No port forwarding, no triggering, no DMZ, etc.
It worked!!! Both 360's were able to find games and reported my NAT type as "Open"!! That's it, that's all that had to be done was buy the right router. That kind of explains why some folks have the problem and some don't. I doubt a lot of folks would be silly enough (or stubborn enough) to buy multiple N routers in an attempt to solve this.
I'm not quite sure why this is the case. It might be that Linksys is being to strict with some aspect of port filtering/NAT routing or that their implementation of uPnP is not quite right (it is a draft standard, after all). Or it could be that Netgear has simply figured out how to handle uPnP better than Linksys. Who knows.
The short answer is buy a Netgear router.