Проблема решаеться удалением ветки реестра:
HKEY_LOCAL_MACHINE\Software\Microsoft\MSLicensing
Заходим regedit и полностью удаляем ветку. Перезагружаем компьютер.
Далее, чтобы не было ошибки "Удаленный сеанс был отключен из-за сбоя создания хранилища лицензий сзапретом доступа", нужно запустить mstsc от имени администратора.
p.s. вариант запуска mstsc /admin не помог решению вопроса, т.к. у пользователя нет прав в терминальном сервере. А вот запуск с правой кнопки мыши от имени администратора, решил вопрос.