Actiontec modems
Linux boxes have difficulty connecting through Actiontec modems. The problem is that the modem supplies its own IP address as one of the nameservers, and it is apparenly non-standard enough so this will not work with our boxen.
Static ip solution
Set the linux box to a static IP in 192.168.0.x range, with a gateway of 192.168.0.1 and subnet mask of 255.255.255.0, and give it static dns address(es). The DNS address will vary from one ISP to another, but may generally be found by searching on google for "<ISP name> DNS server".
You need to edit /etc/network/interfaces to set the static IP
Edit /etc/resolv.conf to set the nameservers on a Debian box. On Ubuntu, both IP and DNS can be set with System>Administration>Networking.
bind9 solution
The following solution has been tested on several boxes now and seems to work well, without the hassle of static ip configuration. Especially good is that the box will still work if connected to a different network.
apt-get install bind9 echo 'supersede domain-name-servers 127.0.0.1;' >> /etc/dhclient.conf dhclient
You might want to add the resolvconf utility which has been seen to help on a dapper box
apt-get install resolvconf