My Vista lab box presented this error when I tried to login into my company’s domain after several months of not doing so:
Trust relationship between this workstation & primary domain failed
I suspected my [Vista] installation was using cached domain information to login, which was the case and why it was being denied access. This is because a computer that is not active for a certain period, is usually removed as a member of the domain.
If you encounter this, you’ll need to rejoin the computer to the domain via My Computer > Properties > Computer Name > Change (you may need Help Desk/IT to do it for you).