Server not found in Kerberos Database

[kneofyte]

>   When I am trying to do a kinit on the client, I am getting this error. However, I have no idea of the log files on the KDC (which I assume should be on the AD server). 

Yes you need to check on the "Security event log" on AD.
Have you checked on the document at:
http://www.microsoft.com/technet/prodtechnol/windowsserver2003/technologies/security/tkerberr.mspx
If above does not help, please also paste the exact "kinit" command that 
you are typing(Ofcourse you could mask the sensitive data).

>   I found out that this error was eliminated when i tried to rename the client machine. e.g. I had the name of the client as test1.mydomain.com and now i changed it to test2.mydomain.com.
>   Can you please help in exactly pinpointing why this could have happened?

Does test1 have a valid account on domain.com?

-Neo