My 8.1 machine locked-up yesterday and I had a lot of trouble getting it to restart...once it did it froze for a while, then seemed to return to normal fter around 10 minutes. After this my VPN connection stopped working (stuck on Verifying Credentials). I deleted the VPN connection and recreated after which I got this error:
error 0x800b0109 a certificate chain processed but terminated in a root certificate
I tried recreating it a number of times and rebooting machine etc, but still seeing same error whatever I did.
I think the error is indicating that a certificate is not installed on the machine...I suspect it might have been corrupted.
Anyway, my fix was to simply restore my machine to a point 2 days previous before the issue occurred using System Restore: http://windows.microsoft.com/en-GB/windows-8/restore-refresh-reset-pc