I've just setup a new RDS Deployment on a 2012 R2 domain. When client's connect to the RemoteDesktop there is a considerable delay at the "Preparing the destination computer" stage. I can resolve this by disabling the Windows Firewall on the RDS Session host computer.
I've searched the web and checked all open ports and it appears I've added the required exceptions for everything, but this is still happening whenever I turn the Firewall Back on.
Check the Security log when the Firewall is on and see if you can find any blocked entries from the IP that's connecting.
Also, check the number of rules in the Firewall and consider disabling/deleting some extraneous ones if there are a lot; if there are too many rules it can actually slow down the response time because it has to process every rule.
From the client, while you are waiting at the "preparing" stage (with the firewall enabled), open cmd and use the following command: netstat -an
Then, in the output, look for a line where the state is "syn sent", this should help you to find the destination port and the address blocked by the firewall.