Cached Credential Issue (Seems to be)

I have a user that has to restart his laptop 3-4 times before the machine lets him logon without being connected to the domain. Every time he attempts to logon he gets “the domain cannot be found or is unavailable” until it finally accepts the cached credentials.

Has anyone seen this type of issue?