DHCP Client Won't Start

This is a new one on me, and very puzzling. If anyone has any ideas, PLEASE
chime in.

I have a client with a Windows XP Pro, SP3 notebook. A couple of weeks ago,
they could no longer connect it to their DHCP server. In trying to find the
problem, I did find that it had a root kit, AV killer, which I think I got
rid of. However, when I start the system, the DHCP client service will not
start. It is set to Automatic. As near as I can tell, the dependency
services/drivers are going. It just won't start on it's own. If I go to the
services console, I can start it manually.

I have tried the published procedures for repairing the Winsock and the
TCP/IP stack. No help.

The problem exists for both the wired and the wireless connections. I have
tried uninstalling both of those and letting them reinstall; still no help.