I saw a few of these cases during our 3000 machine deployment. I found two things that seemed to be the cause:
1)In 90% of the cases the machine in question had never been rebooted after the initial install. Like you mentioned, rebooting the machine took care of the problem and it never happened on that machine again.
2)I recently ran into a problem where the license wouldn't stay activated, but the machine was receiving updates from the server normally. It ended up being that there were mismatched DNS entries on our DNS servers. Deleting the incorrect DNS entry resolved the issue.