Problems replacing wireless router w/ new wireless router

I have Time Warner Roadrunner cable, RCA cable modem, Linksys BEFW11S4 wireless broadband router, 1 wired computer, 2 wireless (802.11b) computers.

This Christmas we got 2 new notebook computers w/ Vista. We couldn't get either one to connect to the wireless with faster than dial-up speeds, and were advised to get a new router that would work with Vista. I picked up a Linksys WRT110 today, it seemed like a good basic router and got good reviews.

The BEFW11S4 was set up with its default settings, and worked fine. I went through the CD that came with the WRT110 and let it do the setup. I couldn't get it to connect to the internet, even with a wired computer. I switched back and forth between the 2 routers, reset everything, the old one would work, the new one when configured exactly the same would not. Strangely though about the 5th time I plugged in the WRT110 and reset it, it let the wired computer connect. I turn on the 2 new Vista laptops and they connect to the router, but report "limited connectivity" and do not have any connection to the internet. With the old router they would connect to the internet, they would just connect at a very slow speed. I've read a lot in the Linksys forum and the only things I've seen that might apply to me are to change MTU and to change the wireless channel. Any other suggestions? Is there something else I've overlooked? Is this a Vista problem and not a router configuration problem?