PCs won’t connect to DHCP on 10.4.11 server

I am running 10.4.11 server on a G5. It's being used as a file server and DHCP server (~15 mac clients and 3 PC clients). The server has been working well for some time, but it was only a 10 use license. Yesterday we wiped it out and rebuilt using an unlimited license. All the Macs can connect just fine, however, the 3 PCs will not get an IP address. There is no firewall running on the PCs. Renewing the IP in the command line gives a rather generic error about the connection timing out. I have tried static routes, but no change. We connected an Airport base station to the network, and the one PC with wireless can connect just fine. Are there any basic settings i'm missing here? Everything works just fine on the Mac side - just can't see what would be different on the PC, especially since this all worked two days ago...