Solved Two Xboxes, 1 router

[gcnd0001]

I have two Xboxes successfully sharing one internet connection to connect to LIVE but there is a problem.
We cannot play together.
ex. I host a party, he cannot join. and vice-versa
Somebody else hosts a party and we both can join.
I host a lobby or game and he cannot join. and vice-versa
Somebody else hosts a lobby or game and we both can join.

Why is this? We both have open NAT, and perfect connection.
My speeds are 15Mb down and 3-5Mb up.
We are both using Internet Connection Sharing from different computers.

 

[Cole Goodyear]

Try giving the xboxs static IP addresses

 

[gcnd0001]

I did, it didn't help.
I tried;
DMZ and port forwarding
UPnP - which is what I am using now
Static Ip's
Dynamic Ip's
and so many more I can't remember.

 

[Strongside]

try using wireless w/o the computer/laptop or an ethnet cord

 

[gcnd0001]

We don't have the wireless adapters and are to far from the router to run an Ethernet.