Hi Guys -
I had this same problem over the weekend and it did take me awhile to figure things out and FIX the problem. After reading all the threads here and on other sites I pieced a few things together and found the problem.
First off - Rob Brooks Blison's Blog - was a good clue, but not the exact problem. What helped me there was him going to the event log and searching out the cause of the problem. That's very important - GO TO YOUR EVENT LOG.
Second - Someone here said that they could create an NEW Admin user, but not a Normal users. I discovered that to be the same with me. I couldn't even turn on and log in as a GUEST user. (Although I do remember doing that about 6 months ago when I had a guest staying with me).
So, anyway, what it ALL came down to was a file in the hidden DEFAULT user folder. The file was; "C:\Users\Default\AppData\Local\Microsoft\Windows Live\SqmApi\SqmData720896_00.sqm"
Turns out that after viewing the properties of this file it did NOT allow normal users permission to access the file. Therefore when Window tryed to copy it when creating the new user folders - access was DENIED and the login process was stopped with the "User Profile Service failed".
Now I don't know what this file is, but I DO know it was created on 3/30/09 and that just so happens to be the same date that WINDOWS UPDATE uploaded Windows Live Essentials to my computer.
So it seems to me that my problem was caused by a Microsoft update that had the wrong user rights assign to a file. I think all the talk of doing Complete reinstalls and trying to fix the Register and such is to much for most to deal with. Many people who recieved the Windows Live Essentials update will have this same problem and it can be fix by another update from Microsoft.
Thanks guys for being here. I have learned much, and will continue to do so with your help.
RoyBoyDenver