Please take a look at this Microsoft article, which offers three possible solutions to your problem.
You receive a "The User Profile Service failed the logon
You may also want to consider a Repair Install:
Repair Install
You could also boot into Safe Mode and try creating a new profile from there.
Lastly, have you tried a system restore to a point in time before the problem arose?