i.e. Remote Desktop can't connect to the remote computer for one of these reasons:

1) Remote access to the server if not enabled

2) The remote computer is turned off

3) The remote computer is not available on the network

Make sure the remote computer is turned on and connected to the network, and that remote access is enabled.

After a lot of time trying to work out why this single user could not connect we found an error in the Security Event Log looking similar to that shown below.
NOTE: The Server Manager\Remote Desktop Services\Servers screen in Windows Server 2012 shows Event Log information but it appears that it doesn't show everything relevant, because this error didn’t appear there so we chased our tails for a long time before actually finding this error in the Security Event Log.

------------------------------------------------

Log Name:      Security
Source:        Microsoft-Windows-Security-Auditing
Date:          29/07/2014 15:27:57
Event ID:      4625
Task Category: Logon
Level:         Information
Keywords:      Audit Failure
User:          N/A
Computer:      myserver.mydomain.local

Description:
An account failed to log on.

Subject:
    Security ID:        NULL SID
    Account Name:        -
    Account Domain:        -
    Logon ID:        0x0

Logon Type:            3

Account For Which Logon Failed:
    Security ID:        NULL SID
    Account Name:        myusername
    Account Domain:        mydomain

Failure Information:
    Failure Reason:        An Error occured during Logon.
    Status:            0xC000035B
    Sub Status:        0x0

Process Information:
    Caller Process ID:    0x0
    Caller Process Name:    -

Network Information:
    Workstation Name:    remotepcname
    Source Network Address:    -
    Source Port:        -

Detailed Authentication Information:
    Logon Process:       
    Authentication Package:    NTLM
    Transited Services:    -
    Package Name (NTLM only):    -
    Key Length:        0

This event is generated when a logon request fails. The Subject fields indicate the account on the local system which requested the logon. This is most commonly a service such as the Server service, or a local process such as Winlogon.exe or Services.exe.

The Logon Type field indicates the kind of logon that was requested. The most common types are 2 (interactive) and 3 (network).

The Process Information fields indicate which account and process on the system requested the logon.

The Network Information fields indicate where a remote logon request originated. Workstation name is not always available and may be left blank in some cases.

The authentication information fields provide detailed information about this specific logon request.
    - Transited services indicate which intermediate services have participated in this logon request.
    - Package name indicates which sub-protocol was used among the NTLM protocols.
    - Key length indicates the length of the generated session key. This will be 0 if no session key was requested.

------------------------------------------------------------------

After researching this error it turned out that the problem was caused by a local policy setting on the remote PC (not the server). The policy that needed changes was:

Computer Configuration->Windows Settings->Security Settings – Network security:LAN Manager authentication level.

The default on Windows 7 & 8 is to not have any value set for this setting, though this particular user's PC it was set to "Send LM and NTLM - use NTLMv2 session security if negotiated "; it needs to be set to “Send NTLMV2 response only”. Once this was done the Windows 8.1 PC was able to open RemoteApp applications without problems.

This setting can be changed using the local group policy editor on the PC (run gpedit.msc) and changing the values as shown below: