DHCP No Longer Available in Win 98

We’ve been running DHCP on our network for four years now. All of a sudden I am getting machines that worked fine before that are claim no available DHCP server. What’s going on here. At first I thought I had run out of avalailable IP addresses, but my DHCP server claims that only 66% of the addresses are actually being used. Any hints?