Acabamos de ter esse mesmo problema com um WS2008R2 e um Mac.
Conectado a partir do mac via programa RDP microsoft. De repente desconectado com essa mensagem.
Tentativas subseqüentes no logon do Mac deram a mesma mensagem e desconexão imediata.
As configurações no servidor eram como user23294 mencionadas, definidas como compatíveis e a configuração funcionou bem até agora (muitos meses).
A solução era fazer logon de um cliente Windows, fechar programas e fazer logoff do usuário.
Em seguida, o usuário pode fazer login novamente em um Mac.
Aparentemente, a sessão do usuário foi corrompida de alguma forma, impedindo o acesso de um Mac, mas não de outro cliente Windows.