Holy crap you have an awkward setup. No wonder you're having trouble.
1. I'm not familiar with Live's port arrangements, but if the 360 must be able to receive connections (as opposed to receiving data over an outgoing connection created by the 360), then the router must be configured to NAT traffic on the Live ports to the 360's IP address. If you're certain you're doing this, then proceed to step 2.
2. You're using a desktop PC as either a router or a bridge. If configured as a router (two different IP subnets), then the PC would also have to NAT its traffic between the wifi NIC and the wired NIC. What are the IP's on the wireless NIC and the wired NIC?
I think you're asking for trouble with that setup unless you know exactly what you're doing, and I'm having trouble visualizing things clearly enough to tell you exactly how to go about troubleshooting it, sight unseen. I use Linux PC's as NAT routers between two subnets, but not Windows boxes (it would require separate software for desktop Windows, which doesn't do NAT out of the box).
Try this test that the router's NAT is configured properly by moving either the router or the 360 close enough together to plug the 360 directly into the router. If the router properly NAT's traffic back to the 360, then you know the problem lies in the routing or bridging going on with the downstairs PC.
You know you can buy a wireless gaming bridge for the 360 (or any wired ethernet device) that costs $50-$60 or maybe less, and it would eliminate problems like this. If you know what you're doing you CAN do the same with your setup, but you have to know how to properly configure everything, while the wireless gaming bridge will be pretty much plug & play.
I had a setup like this for a while. I wanted to run wired devices (xbox, tivo, and other desktops w/ wired connections) at my parents' house in my bedroom that only had wireless. I was able to get it to work w/ some sort of NAT software after a ton of trouble. I was basically using my desktop as a separate router.
I finally just ran a piece of cat5 up to that room from the basement b/c the setup was less than great, and when windows died I got sick of trying to figure out how to get it to work again. FYI I don't remember the app I was using, but it was an outdated and unsupported piece of software that was not user friendly at all.
A quick google search brought up this http//www.nat32.com/
I'd give that a try.
Wow after three days of trying to figure this out you won't believe why it wasn't working. After I posted this message I spent a few more hours online trying everything I could to fix it and this what I came up with.
I found this one website and It said something about updating the firmware and turning the UPnp off. I found the latest firmware upgrade on the linksys website and i believe it came out in 06. The last time the router was updated was in 04. No wonder I had problems with it. So I did all that, turned the 360 on, tested the connection. And NAT is OPEN. Finally haha. Problem fixed.
So all i had to do was.
upgrade firmware. Turn UPNp off. Thanks for all the help guys.
Haha yeah...A few months ago I couldn't get my wireless network adapter for my 360 to work after I got a new router.
However my live subscription ended so I didn't really care to fix it.
Then like last month I bought an extension card, and to fix it all I did was update the firmware.
The router firmware version I had was notorious for having problems connecting with the wireless adapter for the 360.
Wow - the 1st thing I do with a router is upgrade the firmware....
Aright my NAT is moderate I need your guys' help again