The name or SID of the domain specified is inconsistent with the trust

[! confused]

The error message is:
The name or security ID (SID) of the domain specified is
inconsistent with the trust information for that domain
Please try again or consult your system administrator.

I have two domains, one is Mixed mode, the new one is
2003 Native mode. I have a two way trust between them.
The old domain is london.company-name.co.uk
The new domain is company-name.co.uk
I have reciprocating DNS to a DC in each domain (that is,
dc1.london.company-name.co.uk has a secondary zone of
company-name.co.uk and vice versa)

The error comes when I create a member server (2003) in
the new domain. I can add the new server to the domain,
but when I reboot and try to log in, I get the above
error message.
I have looked this up, and there is no information
anywhere other than the error message, and a vague
reference to not being able to contact the domain
controller. The new member server has primary and
secondary DNS set to be the DCs for the new domain for
which it is a member of.
I tried removing the trust, and this did not help...

Can anyone help?