Windows DHCP updating Linux DNS

Hi, We have a W2K3 DHCP server with a Linux DNS server. The problem is that the DHCP clients are not dynamically updating the DNS. I have set the DNS server IP in the DHCP scope but no entries are made. We have set the DNS to allow all, but still nothing. Any ideas?