This issue is caused by the Network Level Authentication (NLA) protocol on the user's machine. NLA is useful if your organization has an internal Certificate Authority and auto-enrollment configured. Otherwise, it needs to be properly configured to allow the remote connections to go through.
Follow the steps below to configure NLA on the user's machine.
- Go to Start -> Run and launch gpedit.msc.
- In the Group Policy Editor, go to Computer Configuration -> Windows Settings -> Security Settings -> Local Policy -> Security Options.
- Find the Network security: LAN Manager authentication level key and double click it.
- Set its value to Send NTLMV2 response only.
- Close the Group Policy Editor.
Once you configure this setting, you should be apple to connect to RemoteApps normally.