It actually depends if the gaming consoles ports are not blocked by your ISP. Moderate NAT type limits your connection playing online games. Strict does not allow you any connection at all while Open allows you to play with everyone online.
Have you had a router before with Open NAT on the gaming consoles? Try to check without the router by going directly to the modem and see if your NAT type is open or strict or moderate. If ever modem is fine and it is the router not working right you can port forward ports on the router.
I found these usual ports online, for XBOX live:TCP and UDP ports: 80-88, 3074-3074, 4267-4269. For PS380, 443, 3478, 3479, 3480, 5223, 8080 and UDP: 3478, 3479.
You can also refer to this links for instructions:
Setting up port range forwarding on Linksys wireless-N routers and gateways: http://www6.nohold.net/Cisco2/ukp.aspx?vw=1&docid=d9b27a0c1bb9496d8c22d0d55f875ddf_17241.xml&pid=80&respid=0&snid=2&dispid=0&cpage=search
Resolving NAT type issues with gaming consoles through a Linksys router: http://www6.nohold.net/Cisco2/ukp.aspx?pid=80&vw=1&articleid=22385