Most resi-grade, non-apple routers have UPnP on by default, so it should work out of the box. I think I had to do some config on Pakedge re-badged Fortinets to get the Xbox to register as 'Open NAT' instead of 'Moderate' or 'Strict'.

I have seen the issue occur on other hardware but its always resolvable w/ a reboot, so I assume its a one-off connectivity or protocol issue.