Solution 1:

Your cert is either not importing correctly (so that it is associated with its private key), or it's in the wrong place, or it's not the right type of cert.

If you are installing it correctly the properties will tell you that it is associated with it private key, you will also see the key overlay on the cert icon indicating the same thing. If you're not seeing that then it isn't going to work.

As far as location is concerned it should be in the Personal Certificate store for the machine not the user. The correct way to import it so that it goes in the right place is to open the MMC as administrator, add the Certificates plug in and select the option to use the computer account. Then select the personal store, right click, All Tasks and then import from there.

However it seems most likely to me that the certificate does not have the correct Extended Key Usage OID value in the EKU list. For a certificate to be used for RDP it must have Server Authentication ( 1.3.6.1.5.5.7.3.1 ) somewhere in the list. This is mentioned as the required OID in this Technet article that expands on the requirements for TS certificates in a bit more detail.

There is also a chance that you may have problems if the server name does not match the certificate name - I can't find anything that says they must match but it wouldn't surprise me if they had to.