Solution Time!
Special Thanks for @gtrig for tipping me off the real issue behind the error.
Why the Error
The error cause as a result of a Microsoft security patch (KB2661254) adding a restriction to certificate validation. This patch requires the certificate RSA key to be greater than or equal to 1024bits. The given siteminder.cer contains a 512bits RSA key. The following link would explain the issue in detail.
http://blogs.technet.com/b/rmilne/archive/2012/09/03/important-upcoming-certificate-changes.aspx
The solution in detail is here. http://support.microsoft.com/kb/2661254
But for me only adding the following regedit key did the trick. HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Cryptography\OID\EncodingType 0\CertDllCreateCertificateChainEngine\Config
minRSAPubKeyBitLength : Decimal 512
To apply this registry modification open command prompt (Make sure the user has admin privileges, else start command prompt Administrator mode) and execute
certutil -setreg chain\minRSAPubKeyBitLength 512
However I would recommend reading through the entire solution from the above link in depth to find unique solution.
Important: This is not recommended approach in a client environment as this may possibly compromise the security of the server environment.
Recommended solution is to have a new certificate created with at least the minimum key size of 1024 (although 2048 is recommended)