I don't know much about the airport, but as you describe your setup you basically have a router behind a router so are doing double NAT for you or consoles.
I'm surprised that you have ever got one of the consoles to connect to be honest! I know the Xbox can have big issues dealing with NAT sometimes and is highly unlikely to work with double NAT.
Your best answer is to replace the second router with a normal network switch. or plug everything directly into the first router.