Cannot login to domain controller

The problem:

"Windows cannot connect to the domain, either because the domain controller
is down or otherwise unavailable, or because your computer account was not
found. Please try again later. If this message continues to appear, contact
your system administrator for assistance."

For the most part everything is working fine. Occasionally I’ll get the
above message and I can fix it by leaving the domain and joining it again.
Sometimes the problem will come back in a few days, sometimes weeks later. On
other workstations after correcting it once the problem never returns.

I don’t see any errors generated in the workstation or domain controller
event logs. The workstation has the correct DNS for the domain controller. It
can ping the DNS controller. It can leave and join the domain with no
problems at all.

The problem seems to happen mostly to laptop users that take their PC away
from the domain for a few days, but it’s not isolated to these users. It has
happened to desktop users too.

The server is running Windows Server 2003 R2. It’s connected to another
domain controller via a VPN using Logmein Hamachi. I have another location
with the same configuration with but it does not experience the same

Any ideas on what can be causing the problem?