Sharing a Verizon ADSL Connection

MY office just signed up for Verizon ADSL service and I'm having a strange problem with DNS.

Some machines on the LAN can get out to the internet just fine. Other machines can not get out to see web pages. The reason I believe it's a DNS problem is I can ping all sites using the xxx.xxx.xxx.xxx notation but I can not ping any sites when I use www.yahoo.com. I know it's not the machines because when I set up the machines to access the old dsl connection it connects just fine. We are using a linksys cable/dsl router to connect to the outside world for the new connection. I've tried clearing out the DNS cache with no success.

 

Is each workstation configurated with Obtain an IP Adress automatically and Enabed DNS? Delete any DNS Server Search Order entries. The Linksys cable/dsl router act as a DHCP host and it should provide the DNS as well.