I was getting the following error when trying to login with accounts that had not used a specific machine before:
User Profile Service service failed the logon. User profile cannot be loaded.
The various fixes I found online (including Microsoft) stated it was a corrupt profile and sent you looking in the registry for certain keys, but this user had never logged in to the machine, so it couldn’t be that. Any account which had previously logged in worked fine. I finally tracked it down (with some hints from online).
My issue was caused by the inability to copy a specific file from a sub-folder of the Default user profile. To find this out I checked in the Event Viewer and under the Application events it listed the specific file it was having problems with (in this case under the Local profile, it was a file in the Windows Live folder).
I simply deleted the file (note that you have to show hidden folders to see the Default user profile folder) and the accounts were able to login again.