Finally, I think I got it working.
All you need to do is follow these instructions (carefully)
http://lani78.wordpress.com/2008/08/09/setting-up-a-dns-for-the-local-network/
http://lani78.wordpress.com/2008/08/10/setting-up-a-dhcp-server-on-ubuntu-hardy-heron/
http://lani78.wordpress.com/2008/08/12/dhcp-server-update-dns-records/
I had some linux clients that weren’t updating the DNS records. Turns out they were not sending their hostname. A fix is found here: http://ubuntuforums.org/archive/index.php/t-549612.html
Still one of my servers kept “loosing” it’s dns record. Turns out the nagios check-dhcp was causing the problem, so I just disabled this test.
