The User Profile Service Failed the Logon. User Profile Cannot Be Loaded

I have found a solution to my problem - the default user profile (C:\Users\Default) seemed to lack necessary ACEs. After resetting ACLs and re-enabling inheritance, creation of new profiles worked as expected. See this link for details.

Text of the above link:

I think the problem caused by some security permission changes to the default user account in the path C:\Users.

The solution, unhide Default user by doing (Computer -> Tools -> Folder options -> ) ,

The right click over the Default user -> Properties -> Security -> Advanced then tick the "replace all child object permission entries with inheritable permission from this object" fixes the issue. Basically you are replacing all child object permissions for Default user.

Now you should be able to login.