I had a windows 7 machine providing the above message for new users added to the domain. I found the following fix at:

https://answers.microsoft.com/en-us/windows/forum/windows_7-security/unable-to-log-on-the-user-profile-service-service/2c51ee80-8ff2-4aa6-b532-175b83b9c09a?page=3

Somewhere in the process of modifying the Default User Hive I’ve managed to inadvertendly (and on several occasions so I know it wasn’t just a one time stupid user woops) change some security in the \Users\Default subpaths (without trying to modify their subpaths) and I have found that this three step process works:

Take ownership of the whole branch \Users\Default as an administrator

Take ownership of the whole branch \Users\Default as System

Inherit rights for the whole branch \Users\Default