I have the same issue and I suspect it is that the agent disables TLS 1.0. I also see schannel errors in the event log on the template VM.
if this is windows 7 or/and 2008 check Windows kb3080079 which enables tls1.1 and 1.2 for rdp.
( I've not had a chance to test this as it is the weekend, but that is where I'm going next... )
that worked for me. Rdp is now good, using TLS 1.2.