Are you using a static port on your outbound NAT rule? Port randomisation seems to break various games. I also find denying port 3074 using UPNP ACLs will force some XBL games to retry on other ports and has fixed a few problems.I'm looking at my firewall now and can see about 25 different NAT rules generated by UPNP currently so it appears to be working.FWIW we run gaming events with around 1,000 - 1,200 devices and UPNP worked well for us the past two events we ran.
I solved it by using a rule like this...Gianluca