XP Clients not leasing IP's

Check that there isn't another authorised DHCP server giving out leases on the same IP range.

I went through that Microsoft article already - did not find anything that helped me.  I have not been able to locate another DHCP server on the network - but that thought did occur to me.  I am not entirely sure what the best way to find a rogue DHCP server is, if in fact that is the issue.

A tool in the Windows 2003 Support Tools to help find rogue DHCP servers:

Dhcploc.exe
http://technet2.microsoft.com/WindowsServer/en/library/8fa42e83-ec08-4a9b-9057-8909f7ed433e1033.mspx

i am trying to run DCHP loc on a machine on the network and it is bombing out - either closing unexpectedly or giving a open receive socket failed error - today is not my day :)

Rogue DHCP: (added to the comments above, please credit the folks who mentioned a rogue DHCP server)
Can you go to the router and mass storage devices and check to see if they are supplying DHCP. Those are the two nodes that most often cause a rougue DHCP server to be active. All Microsoft DHCP servers need to be manually authorized before coming on line. So, you will know when they come on line.

ISA is another culprite that can knock down a DHCP server. ISA has rules that need to be configured to allow DHCP. But, if you are getting a NACK from the server that means your DHCP request from the client is getting through on IP 0.0.0.0 and subnet 255.255.255.255. Since you were able to receive a IP broadcast from the client, ISA may not be the culprite. If you think ISA is underconfigured to provide DHCP, then google search "ISA rules for DHCP". I have seen ISA prevent server replies to client DHCP discoveries.

You should check the server's IP address and make sure it is on the same subnet as the scope of the DHCP service. Regard;ess of what subnet, the DHCP server recieves the discovery from the client on IP 0.0.0.0 and subnet 255.255.255.255. Also make sure the server has a fixed IP that is not in the scope of the DHCP server.

One other think to check is to see if your xp clients have IP version 6 on them.

Last, but not least, the router may have prevented the server from sending a reply back to the client.

Here is a link of folks that had the same error as you that are providing answers.
http://www.eventid.net/display.asp?eventid=1002&eventno=1778&source=Dhcp&phase=1

Here is the basics of DHCP: (not very basic, but gives you the roots of how DHCP requests traffic). This link may provid you with the ammo to better read the NACK errors in the DHCP logs.
http://support.microsoft.com/kb/169289

I hope this helps

The network is a multiple VLAN network - 3 VLAN's - server, wired client, wireless client - the DHCP server is statically on the server subnet - its fixed IP is not in any scope - therer are only scopes for the wired and wireless - users have informed me that they are able to lease IP's from the wireless scope, not the wired - I have yet to confirm that - the Cisco layer 3 switches all have the IP of the DHCP server as a helper to forward the DHCP requests - there is no ISA server on the network.  I am actually not the "network guy" although I have some experience - I am just not receiving much help at the moment so I am trying to get a solution working on my own.  But that's another story :)

Onsite staff came in and did a packet capture using wireshark from a workstation - issues pointed to the core layer 3 switch experincing a broadcast storm of some sort - they did a hard reboot of the switch and the issue resolved itself - in this situation I would say the switch is really the router so ChiefIT's suggestion would be correct.

It's actually something I would have done much sooner if I was on the netowork team and onsite -but in this case my job starts and stops at servers for the most part.