Force DHCP to get a new name
Some DHCP systems assign a DNS name based on the reported hostname that a box gives the first time it requests a DHCP address. For instance, at my work, each Windoze box is assigned a unique name when it's built. Then, the first it is connected to the network, its MAC address is associated with that name in the DHCP system and it gets assigned a DNS name, i.e. <name>.company.com.
This can cause some annoying issues when doing a Debian install on the network. If you choose the default box name (maybe you don't know what the real name is yet) you'll get a box named "debian". In a corporate DHCP system like I described above, that will get you a DNS name of debian.company.com. Then, even when you change the box's name in /etc/hostname or whatever, the DNS name won't ever get updated in the system.
A friend suggests these two fixes for the DHCP3 client, which involve editing a DHCP configuration file. The file might vary depending on what distribution you're using. For Ubuntu, it seems to be /etc/dhcp3/dhclinet.conf. For a Knoppix-based install, it seems to be /etc/dhcp3/dhcp.conf. I'm not sure what it will be in a standard Debian install. In either case, edit the file, and add:
send host name "yourname";
Then, run:
/etc/init.d/networking restart
That should take care of it.