My solution was to rename the terminal services profile and create a new one.
It appears that at least on my image this was happening because when the default user profile was copied, no permissions were granted under the "allowed to use". I re-copied the template profile to the default user profile, and allowed PCNAME\Everyone to use. After doing that, and deleting the user's profile, it began working. I also had to delete the network/roaming profile as it still had the incorrect permissions stuck in it, so when it was loaded it re-created the problem.
I encountered the same problem with roaming profile on Terminal Server. Event 111 followed by Event1085 from source Userenv. The user seems to have lost the rights to his registry hive (HKCU). I loaded the user's ntuser.dat in regedt32 and granted him the rights.
In my case, a different user had access permissions to HKCU. Removed this user and added the correct user with Full Control permissions.
In my case, the user did not have sufficient rights to open HKCU. You can use regedt32 to grant Read/Write to it to this registry key. I granted R/W to Domain Users before copying as a mandatory profile.
In my case, only two user accounts have generated this error. It happens when they log on to a machine not their own. When they sit at their own desk, there is no problem. Group policy is redirecting "My Documents" to a network home directory. See Event ID 1000 from source Userenv for more details.