Did you do an upgrade, or fresh install?

Upgraded from Windows 2000 Server running SP4

Try fresh install, if you can do that withouth loss of data

Is it the only DC on the network? If so, it could be that the server is not authenticating in time to start services properly. You also checked the reg keys mentioned here?
 
http://support.microsoft.com/default.aspx?scid=kb;en-us;314494

It is the only DC on the network.
 
The link you provided is for Windows XP computers. I am currently having those issues on Windows XP clients. But at least they log the error only once when I log in.
 
The Win2k3 server logs the two errors every 5 minutes on the dot.
 
What can I do to make sure it is authenicating properly before the services start? These errors never occurred on Windows 2000 Server.

Try to resolve the errors on the clients if possible utilizing that link, and it might address the server. Also, did you use any policies with registry key limitations? The policies that worked fine in Windows 2000 do not necessarily work in Windows Server 2003 due to the SERVICE account being split into "LOCAL SERVICE" and "NETWORK SERVICE". Also, the "LOCAL SERVICE" account now holds many permissions in the registry that the "SERVICE" account never needed in Windows 2000. Review the DC policy and see if there are any registry keys (like winreg) that have limited permissions applied. Just because you have disabled portions of it, this might not clear all of it (yeah, GPs are wierd that way, that's why we always have clean backups for our labs).
 
Also, this may be obvious, but is the "SYSVOL" share coming up?

SYSVOL share is coming up fine.
 
I have tried to correct the errors on my clients with the links given, yet I continue to get them. No idea on what to do next on that.