Why does Window's SSL Cipher-Suite get restricted under certain SSL certificates?

If the certificate being used on the server was generated using the Legacy Key option in the certificate request form, the private key for that certificate will be stored in Microsoft's legacy Cryptographic API framework. When the web server tries to process requests using its new, Cryptographic Next Generation (CNG) framework, it appears that something related to the RSA private key stored in the legacy framework is unavailable to the new framework. As a result, the use of the RSA cipher suites is severely limited.

Solution:
Generate the certificate request using the CNG Key template in the custom certificate request wizard.

MMC | Local Computer Certificate Manager | Personal Certificates Folder | (right click) | All Tasks -> Advanced Operations | Create Custom Request | "Proceed without enrollment policy" | select "(no template) CNG key" | proceed to complete the certificate request according to your needs.

Verifying that the key is in the right place:
http://msdn.microsoft.com/en-us/library/bb204778(VS.85).aspx
http://www.jensign.com/KeyPal/index.html

Tools for verifying correct cipher-suites:
http://pentestit.com/2010/05/16/ssltls-audit-audit-web-servers-ssl-ciphers/
https://www.ssllabs.com/

SSL cipher-suite settings:
http://support.microsoft.com/kb/245030
http://blogs.technet.com/b/steriley/archive/2007/11/06/changing-the-ssl-cipher-order-in-internet-explorer-7-on-windows-vista.aspx

This took us a week to figure out. I hope this saves someone the same trouble.

Got this exact same issue myself and this post saved me a ton of time so thanks all!

Gary's solution is spot on but I managed to solve the issue simply by converting the PFX to PEM and then back to PFX again using openssl. The new PFX imported the certificate in IIS just the same with the difference that I can see the missing ciphers.

This is how:

openssl pkcs12 -in mycert.pfx -out mycert.cer -nodes

Then split the cer file in three, the key, the certificate and the intermediate certificate[s]

openssl pkcs12 -export -out mycert-new.pfx -inkey mycert.key \
-in mycert.crt -certfile mycert-intermediate.crt

Then if you import the new .pfx file into IIS it will use all the ciphers you expect to see.

So no need to reissue the certificate.