I am on a 172.16.x.x network with about 60 Windows XP home and Vista home clients in a peer-to-peer workgroup that uses DHCP to assign addresses. About half the traffic on my LAN is netbios broadcast. I do not want to do a WINS server because I do not want to have to manually change the registry on every machine. This is only for local name resolution and I do not have any web servers or e-mail servers. I do not have access to a Windows server to use as a DNS server. I am on Debian and using BIND but am open to other suggestions.

I found this guide, but it looks like I have to manually add the host name and IP address of every host:

http://www.zaphu.com/2007/09/14/ubun...-server-setup/

Is there any to have the DNS records populate themselves?

You can use nsupdate in tandem with the DHCP assignments.

Here we actually have a Windows DNS (MS DNS) server for internal lookups so I've not used nsupdate myself but have seen it mentioned often in the BIND mailing list.

The link here may help but as I said I haven't used it myself:
http://linux.yyz.us/nsupdate/