Today I was assisting a friend of mine here from TMG team that was facing this issue, same issue that was also mentioned on this thread. The problem was happening when using Cryptography Next Generation (CNG) or also called V3, TMG was not recognizing the private key and was showing up this error message. This is a known issue because TMG (and ISA) don’t support CNG (V3 Certificates). This is well documented under the unsupported documentation here:
Issue: Forefront TMG does not support the use of certificates created using CNG (Certificate New Generation) based templates for Web listeners or as client certificate authentication in Web publishing or Web chaining rules.
Cause: CNG certificates are not usable by Forefront TMG.
Workaround: Create certificates using Windows 2000 or Windows 2003 templates.
Again, make sure to read this unsupported document before deploy TMG, there you will find the official statement from TMG Product Team about what it is supposed to work and what it is not.
Note: Important to emphasize that CNG V3 is not X.509 V3. CNG V3 refers to the new V3 Certificate Template on 2008 while X.509 V3 is the current certificate standard in which TMG is fully compatible.
Over a year later and it's still broken. I'd like to publish some sites but I can't get the keys working without jumping through a ton of hoops. Hopefully Microsoft will pull it's head out of it's backside and fix this.
Is not that is broken, it is not supported and this is documented as shown above. AFAIK there is no plans to change the support statement for TMG.
for me, this was the solution to use a CNG template created Certificate on TMG: