That's exactly what it is. Both boxes are "Fighting" each other to get those pakages, and it's all useless since they're colliding even on the connection phase.
You have to separate those xbox and asign different IP's to each one, and then, redirect or forward the ports.
Here, just in case you need an example:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
S= Source port D= Destination PortOutgoing from Xbox, to the gateway (Router)
XBOX 1 -> (Port S:3074 D:3074) -> Gateway -> XBOX LIVE
XBOX 2 -> (Port S:3074 D:3074) -> Gateway -> XBOX LIVE
Outgoing from Gateway to Xbox Live Servers
GATEWAY -> (Port S:20001 D:3074) -> XBOX LIVE
GATEWAY -> (Port S:20002 D:3074) -> XBOX LIVE
And the return traffic from Xbox Live back to the Xboxes (via the gatway, which is kinda transparent to the Xboxes)
XBOX LIVE -> (Port S:3074 D:20001) -> GATEWAY -> XBOX 1
XBOX LIVE -> (Port S:3074 D:20002) -> GATEWAY -> XBOX 2
Of course, every single unique new connection automatically gets a port assigned to it from the pool in the range 20000 -> 30000, you could set it to a wider range (the highest port number available is 65110, I think...). When a connection state is dropped (i.e you log off and disconnect) the allocated port is freed up on the Gateway (basic IP stuff).
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Hope it helps.