I setup a Cisco router recent with just basic NAT. I use an Gigabit Ethernet interface for WAN, and one for LAN. There are no firewall policies. There is only an IP pool to hand out internal DHCP. This works fine when I am the only one connected but as soon as people use the connection it kills it. By killing dns lookup works fast but the site connections are very slow, i.e. going to www.cnn.com could take 30-45 seconds. I have a 12/1Mbit connection, so connection is not the problem. Also my network runs just fine on a Linksys WRT54GS. I can post config if necessary.
I have this problem too.