This is definitely in my top 10 list of most frustrating errors. There are about 100 different solutions floating around and sometimes one of them works and sometimes none of them work. Well here is solution 101...
The error of course happens as you log onto a computer with a domain profile. It takes a long time to load and then you get a message that you were logged on with a temporary profile. Event Viewer will record:
"Windows cannot find the local profile and is logging you on with a temporary profile. Changes you make to this profile will be lost when you log off."
If you aren't particularly worried about whatever was in the profile before, you can sometimes solve this by simply changing the profile directory in Active Directory Users and Computers. Then reboot the machine and log back in.
For example in the pic below, the profile path used to end with a folder called 'newuser' and changing it to just 'new' created the profile folder newly on the server and after rebooting the pc in question, it logged in fine.