I have a slightly awkward setup, but there's no reason why it shouldn't work. I am with Virgin Broadband, so I have a cable coming into the house to a modem, which leads to my Apple Airport wireless device. But from Airport I have an ethernet cable going to a router and from the router I've connected a PS3 and an Xbox 360. Occasionally one of the consoles connects to the internet, but never both at the same time, and just recently neither. I have tried resetting everything (modem, routers, Airport etc.) but nothing.
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.
I think I'll give the network switch a go. I was going to do this before but I thought it would be better to buy a router. Otherwise I was thinking about getting the wireless network adaptors for the consoles.
you can probably turn you second router into a switch by either disabling NAT on it or by disabling DHCP on it setting the router IP address to be outside the normal range of addreses for you LAN and making sure everything is plugged into a LAN connection on it, the WAN interface will not work any longer if you do the above.
I would have no idea how to do any of those things. I think it would be easier to get the wireless adaptors. Thus taking out the second router and making a bit simpler.