I think tomcole is on the right track when he asked you for more information.
I believe the original question stated that AD is not being used. If this is the case, try this URL for
installing DHCP on a standalone server, including where to look when clients don't receive leases..
I'd also recommend using Windows' Network Monitor to trace dhcp related packets which will give you a better idea if it's a routing issue etc.
Check this whitepaper:
Windows 2000 Startup and Logon Traffic Analysis
an excerpt follows:
The process in general consists of eight messages:
DHCPDiscover. A DHCP client uses this message in order to detect at least one DHCP server.
DHCPOffer. Each DHCP server that receives the request from a client checks its scopes for a valid configuration set and offers this to the DHCP client.
DHCPRequest. The DHCP client requests the first offer it receives from the DHCP server.
DHCPAcknowledge. The selected DHCP server uses this message in order to confirm the lease with the DHCP client.
DHCPNack. The DHCP server uses this message in order to inform a client that the requested TCP/IP configuration is invalid.
DHCPDecline. The DHCP client uses this message in order to inform the server that an offered TCP/IP configuration is invalid.
DHCPRelease. The DHCP client uses this message to inform the server that an assigned configuration is no longer in use by the client.
DHCPInform. This is a new message defined in Request for Comments (RFC) 2131. If a client has already obtained an Internet Protocol (IP) address (for example, manual configuration), it may use this message to retrieve additional configuration parameters that are related to the IP address from a DHCP server.