Hi don,
I have a new Dell Optiplex XP system (Broadcom NetXtreme NIC) I set up as a DHCP client. When I enable the LAN interface on it, hundreds of lines of the following show up in the server syslog.
A BIOS upgrade on the offending PC could fix your problem - it has helped us in the past with DHCP problems with a batch of fujitsu siemens PC's
Otherwise you could use dhcpdump to see what is being sent and recieved from the server
Anthony