Kerberos services gives error on Domain Controller startup, Pls help!

I recently started getting error message upon boot up of my Domain Controller (Windows 2003). It give me a popup error that says one of the services failed to start. So i looked in the event viewer and found these two errors:

1.) The Kerberos Key Distribution Center service hung on starting. (Event ID: 7022)
2.) The dynamic deletion of the DNS record '_kerberos._tcp.dc._msdcs.mydomain.pvt. 600 IN SRV 0 100 88 MACHINE-NAME.mydomain.pvt.' failed on the following DNS server:  
DNS server IP address: 192.168.0.99
Returned Response Code (RCODE): 5
Returned Status Code: 9017  
USER ACTION  
To prevent remote computers from connecting unnecessarily to the domain controller, delete the record manually or troubleshoot the failure to dynamically delete the record. To learn more about debugging DNS, see Help and Support Center.  
ADDITIONAL DATA
Error Value: DNS bad key.
(Event ID: 5775)

Then I ran DCDiag and got this:
----------------------------------------------------------
Domain Controller Diagnosis

Performing initial setup:
   Done gathering initial info.

Doing initial required tests

   Testing server: Default-First-Site-Name\MACHINE-NAME
      Starting test: Connectivity
         ......................... MACHINE-NAME passed test Connectivity

Doing primary tests

   Testing server: Default-First-Site-Name\MACHINE-NAME
      Starting test: Replications
         ......................... MACHINE-NAME passed test Replications
      Starting test: NCSecDesc
         ......................... MACHINE-NAME passed test NCSecDesc
      Starting test: NetLogons
         ......................... MACHINE-NAME passed test NetLogons
      Starting test: Advertising
         ......................... MACHINE-NAME passed test Advertising
      Starting test: KnowsOfRoleHolders
         ......................... MACHINE-NAME passed test KnowsOfRoleHolders
      Starting test: RidManager
         ......................... MACHINE-NAME passed test RidManager
      Starting test: MachineAccount
         ......................... MACHINE-NAME passed test MachineAccount
      Starting test: Services
         ......................... MACHINE-NAME passed test Services
      Starting test: ObjectsReplicated
         ......................... MACHINE-NAME passed test ObjectsReplicated
      Starting test: frssysvol
         ......................... MACHINE-NAME passed test frssysvol
      Starting test: frsevent
         ......................... MACHINE-NAME passed test frsevent
      Starting test: kccevent
         An Warning Event occured.  EventID: 0x80000785
            Time Generated: 06/09/2007   12:10:04
            Event String: The attempt to establish a replication link for
         ......................... MACHINE-NAME failed test kccevent
      Starting test: systemlog
         An Error Event occured.  EventID: 0xC0001B6E
            Time Generated: 06/09/2007   11:42:34
            (Event String could not be retrieved)
         An Error Event occured.  EventID: 0xC0001B6E
            Time Generated: 06/09/2007   11:51:57
            (Event String could not be retrieved)
         An Error Event occured.  EventID: 0xC0001B6E
            Time Generated: 06/09/2007   12:07:36
            (Event String could not be retrieved)
         An Error Event occured.  EventID: 0x0000168F
            Time Generated: 06/09/2007   12:11:21
            Event String: The dynamic deletion of the DNS record
         An Error Event occured.  EventID: 0x0000168F
            Time Generated: 06/09/2007   12:11:21
            Event String: The dynamic deletion of the DNS record
         An Error Event occured.  EventID: 0x0000168F
            Time Generated: 06/09/2007   12:11:22
            Event String: The dynamic deletion of the DNS record
         ......................... MACHINE-NAME failed test systemlog
      Starting test: VerifyReferences
         ......................... MACHINE-NAME passed test VerifyReferences

   Running partition tests on : ForestDnsZones
      Starting test: CrossRefValidation
         ......................... ForestDnsZones passed test CrossRefValidation

      Starting test: CheckSDRefDom
         ......................... ForestDnsZones passed test CheckSDRefDom

   Running partition tests on : DomainDnsZones
      Starting test: CrossRefValidation
         ......................... DomainDnsZones passed test CrossRefValidation

      Starting test: CheckSDRefDom
         ......................... DomainDnsZones passed test CheckSDRefDom

   Running partition tests on : Schema
      Starting test: CrossRefValidation
         ......................... Schema passed test CrossRefValidation
      Starting test: CheckSDRefDom
         ......................... Schema passed test CheckSDRefDom

   Running partition tests on : Configuration
      Starting test: CrossRefValidation
         ......................... Configuration passed test CrossRefValidation
      Starting test: CheckSDRefDom
         ......................... Configuration passed test CheckSDRefDom

   Running partition tests on : bemara
      Starting test: CrossRefValidation
         ......................... bemara passed test CrossRefValidation
      Starting test: CheckSDRefDom
         ......................... bemara passed test CheckSDRefDom

   Running enterprise tests on : mydomain.pvt
      Starting test: Intersite
         ......................... mydomain.pvt passed test Intersite
      Starting test: FsmoCheck
         ......................... mydomain.pvt passed test FsmoCheck
-----------------------------------------------------------------------------

This has got me worried since this is the Domain Controller. I don't notice any evident problems from the surface though. All my network computers are able to connect to the network ok. But how do I get rid of these problems?