The security database on the server does not have a computer account for this workstation trust relationship.

We recently has this error message appear when trying to log on Windows 7 workstations to our Windows 2003 domain server.
"The security database on the server does not have a computer account for this workstation trust relationship."
We trawled through the Google searches for this message and there are pages of reports of this error.
Let me give you the circumstances.
Our domain server failed. We could not get it to get through POST and BIOS to try to find and operating system. That was the first big 'Ouch'.
So we rebuilt the server on to new hardware and configured it, as we thought, the same. We initially had some issues with DNS and NICs not doing as they should but the upshot was that our 2 Windows 7 workstations could not connect to the domain. Please note this did not affect our remaining XP workstation which logged just fine.
After looking at the Goggle responses we noticed that we had rebuilt the domain but missed off the '.local' on the domain name.
So we rebuilt being more careful next time. Even so we got a capital letter in the wrong place in the domain name. So we rebuilt a third time. This time we are sure we got everything right. It made not a jot of difference.
Other websites had suggested we disconnect from the domain and reconnect to the new domain. Not an iota of difference.
Finally we had to reinstall the operating system on both our Windows 7 machines.
One side effect of this, despite having installed onto completely new hard disks to preserve the data on the old disk, is that on one of the machines we have lost ALL out Outlook pst files. Some emails going back 6 years with important information.
Couple this with the total data loss of all information on the server did not make us very happy.
I will finish with this comment. Why, oh why, Microsoft is it so hard to get your systems to talk to each other. This is hardly a ringing endorsement for the improvements in Windows 7 when XP performs better in what was already a very fraught situation. Please try to do better next time.