Kerberos errors

We have an ageing Exchange server (2K server, Exchange 2k)
and we are going to migrate this to a new 2K3 server
running Exchange 2K3.

The old box is now generating hundreds of kerberos errors
for no apaprent reason. The new box is running, has
Exchange 2k3 installed as part of the site.

The kerberos errors are all like:

A Kerberos Error Message was received:
on logon session LogonUser
Client Time: DOMAIN.COM/Server$
Server Time:
Error Code: 16:50:9.0000 5/11/2004 (null) 0x18
Extended Error: KDC_ERR_PREAUTH_FAILED
Client Realm:
Client Name:
Server Realm: DOMAIN.COM
Server Name: krbtgt/DOMAIN.COM
Target Name: krbtgt/DOMAIN.COM@DOMAIN.COM
Error Text:
File:
Line:
Error Data is in record data.

(I've changed the domain and server names, they are
correct in the actual error)

I'd appreciate any help anyone can give..
BAzz