[QRS]

Есть ли какие-нибудь логи\скрины ошибок?
Если с Вас спрашивают сертификат, то похоже, что маршрутизатор пропустил трафик на порт 443 и дело не в этом.

Какой сертификат используется - самозаверенный, выданные собственным центром сертификации или выданные уполномоченными центрами?
Если сертификат выдан собственным центром сертификации, то проверьте доступен ли клиенту CRL данного сертификационного центра (для проверки можно закачать свежий CRL, руками установить на клиента и, пока CRL не устарел, проверить работу подключения.

Проблема возникает на этапе подключения к виртуальной машине или при проверке сертификата?
Каким образом в подключении Вы указываете адрес машины, к которой должно пройти подключение? Если не трудно, не могли бы Вы выложить файл подключения?

Непосредственно с TS-Gateway сервера Вы можете подключиться к проблемной виртуальной машине?
Если проблема в сетевом уровне, то помогли бы ipconfig /all с удаленного клиента, TS Gateway и виртуальной машины.