Not a big fan of generic error messages like the above, but that's what I was stuck with when trying to start the DHCP service on one of my Windows Server 2003 boxes. This box was not registering itself in DNS correctly and the DHCP service has to be running for this to work, even if I was not assigning the IP via DHCP.
After a morning hunting around the web I found the following fix...
Grab yourself a copy of Sysinternals tool Process Monitor and run it on the offending server while trying to start the DHCP service. Stop the monitoring then have a look at what registry requests where requested at the same time as trying to start the service. You should notice that some have "access denied" and this is what our original error is referring to. Open regedit and find the offending registry key and give the required permissions to the account the service runs as, for DHCP the "Network Service" account.
This fix has also reportedly worked for other services having the same error when trying to start.
How difficult would it be for Microsoft to provide a more detailed error message? *sigh*
Credits go to: Taz0 on TechNet