krb5kdc_err_s_principal_unknown on Windows Kerberos Domain

[Will]

I may be having problems with Kerberos on a Windows 2000 domain controller,
used with a Windows 2000 or Windows 2003 member server.   I would appreciate
some help in understanding this situation from experienced Kerberos admins
who happen to also have deep Windows experience.

A sniffer trace of our Windows domain member servers shows the member
servers are succeeding in getting tickets from the domain controller for the
domain controller's host ticket, but failing to get tickets for the domain
itself.

By example, member server A is contacting domain controller my-dc1 in
Windows domain hq.corp.com. What I am seeing in the sniffer trace is that
the member server A asks the my-dc1 domain controller in its role as a
Kerberos ticket granter for a ticket to the domain (i.e.,
krbtgt/hq.corp.com). The domain controller is returning
krb5kdc_err_s_principal_unknown.   The following line in the trace shows the
same member server A asking my-dc1 for the Kerberos ticket for the domain
controller krbtgt/my-dc1 and this member server A does obtain.

First, I want to understand what does this failure mean?   I saw many
sniffer traces posted on Google that show the same sequence for other
Windows domains, so apparently it's a common case.

Second, how do I correct this problem?   Someone else told me to create an
SPN for the domain with SetSPN, but I would like to a) get help determining
if we already have such an SPN, b) I would like to understand better what it
is I am creating when I create an SPN, how an SPN is used by member servers,
and what are the effects we are suffering if we don't have an SPN.

Any other ideas on what is causing the krb5kdc_err_s_principal_unknown error
are appreciated.

-- 
Will