I want to say a big THANK YOU for your post. While my problem was similar to yours, my solution was different. It was the research you did to find your solution that helped me, and for that I am very grateful.
With the hope that it will help another reader, I will briefly describe my solution. I actually have Windows 7, but I believe my solution applies to Vista as well.
I tried to add a new Standard User ("Visitor") to my computer. When the user attempted to log in for the first time, we saw the scary message ("The User Profile Service service failed the logon..."); and like you, there was no corrupt registry entry and no backup key to work with.
You wrote that when a user logs in for the first time, Vista uses the contents of c:\users\default as a template; I figured this probably applies to Windows 7, too. You also explained that if Vista can't copy the default profile during the account creation/log in process, then the new user's account won't be created. That was all the information I needed.
A trip to Event Viewer quickly revealed a User Profile General warning in the Application log:
"Windows cannot copy file C:\Users\Default\ to location C:\Users\Visitor\. This error may be caused by network problems or insufficient security rights. DETAIL - Access is denied."
I had been adjusting the access control lists on C:\Users and messed up. It was my own fault. Once I added Users (i.e., the Users group) to the ACLs of \Default, \Default User and \All Users, giving it Read & Execute permissions in each instance, I had no trouble creating new users accounts.