We find that if we rename the PC, then allow more than a day to go by before restarting, this can happen.
Also, if we rename a PC, then the user allows the PC to go into Lock mode (screen saver timeout with login required to return) they will encounter this upon wake up/re-logon.
In the above two cases a reboot usually resolves it, when it doesn't, we go in as local admin and disjoin then rejoin the domain to resolve it.
Also, in the above two cases, we did not lose the computer in active directory, so after the disjoin/rejoin you'd want to remove the orphan computer from AD.
There's an article online somewhere about why you should NOT disjoin and rejoin the domain in this case, but we have always done it this way and have never experienced ill effects.