Remote Desktop Error

I have just recently installed a new network for one of our customers. They are running Server2008 R2 with Hyper V. This server runs 2 Virtual Machines, one is a Domain Controller/ Mail Server/ Print Server and File Server. The second one is a Application server only. The Domain controller is a Windows Server 2008 R2 running Kerio Mail server. Everything runs like it is supposed to. The Application server has Windows Server 2003 R2 and is part of the domain. I have Remote Desktop Enabled with the Administrator having access. When trying to Remote into the Application server via RDP we get an error message

"The computer can't connect to the Remote Computer.
The connection was lost due to a network error. Try connecting again. If the problem continues, contact your network administrator or technical support."

I have tried from a Windows XP Machine, Windows 7, the Host and the Domain Controller. All of them do the exact same thing. When I go back to the Application Server It has an Error in the System Event Log.

" Source TermDD Event ID: 50
Description:
The RDP protocol component "DATA ENCRYPTION" detected an error in the protocol stream and has disconnected the client."

I have tried the suggested stuff at EventID and seen a couple post here about people having this problem in different scenarios. I am hoping someone will be able to help.

Thanks for you help,
Mike