Hmm, very odd that you are having problems.
I've all my equipment on DHCP, and have created static DHCP entries for them.
Of course DNS is pointing to the firewall, as well as Default Gateway.
Then I've enabled UPnP on the Firewall, X-box360 and PS3.
The firewall has UPnP forbidden for everything, except the X-Box360 and PS3's IP addresses.
This works without any sort of problems. They get the best NAT possible both, I see ports open and close according to the different games and states the machines are in.
Here at work I've tried as well, and here I see problems, but my guess is that it has something to do with some of the ancient switches we have here :-(