I have a dhcp server here, running the isc-dhcpd daemon.
Some machines get an IP address fine, from syslog:
Dec 8 08:42:21 nethandler dhcpd: DHCPDISCOVER from 90:e6:ba:f6:xx:xx via eth0
Dec 8 08:42:21 nethandler dhcpd: DHCPOFFER on 10.0.0.202 to 90:e6:ba:f6:xx:xx via eth0
Dec 8 08:42:21 nethandler dhcpd: DHCPREQUEST for 10.0.0.202 (127.0.1.1) from 90:e6:ba:f6:xx:xx via eth0
Dec 8 08:42:21 nethandler dhcpd: DHCPACK on 10.0.0.202 to 90:e6:ba:f6:xx:xx via eth0
Others don't
Dec 8 08:42:04 nethandler dhcpd: DHCPDISCOVER from 08:00:27:d5:xx:xx (WIN-3053MGTDBGP) via eth0
Dec 8 08:42:04 nethandler dhcpd: DHCPOFFER on 10.0.0.132 to 08:00:27:d5:xx:xx (WIN-3053MGTDBGP) via eth0
Dec 8 08:42:08 nethandler dhcpd: DHCPDISCOVER from 08:00:27:d5:xx:xx (WIN-3053MGTDBGP) via eth0
Dec 8 08:42:08 nethandler dhcpd: DHCPOFFER on 10.0.0.132 to 08:00:27:d5:xx:xx (WIN-3053MGTDBGP) via eth0
And continue ad infinatum. I can't find any pattern to the machines that can't connect. Some wireless clients can't connect, some can. An ubuntu vm can connect, a windows 7 vm on the same hardware can. A windows server on the same hardware can't. A few macs here can't.
Any help would be appreciated, or a point to what I can use to further debug the problem.
Try doing a packet capture on the client. dhcpd thinks it's sending out an OFFER, either the client is ignoring it or (more likely) the offer never makes it to the client.
While you're at it, also do a packet capture on the server, and if you can, on something in-between (a SPAN/Mirror port on the switch, router port, etc.).
Look for a DHCP rogue server on your network. There is a free microsoft tool to search. Also, make sure you are using IPhelpers on your switches.