The audit log may say it could not set some attributes such as Allow Logon. In my testing it would occasionally complain about not being able to set other attributes related to Terminal Services as well.
If you go to your AD Agent on the AD server and enable detailed logging you may see something like this:
This is the first clue to the problem. Simply run the agentCfg tool and choose option F. Registry Settings, then option A. Modify non-encrypted registry settings, page down using option D. then set WtsEnabled to 'TRUE'.
Try again to provision your users and this time I think you will have more success.