I came across this error recently while running the Hybrid Configuration Wizard on Exchange 2010 SP2. It caught me out a little and as it turns out the fix is quite simple. It seems the wizard does not recognise certificates that begin with anything other than “CN=”. In my particular case I was being tripped up by a certificate beginning with “E=”. What made this even more confusing was that the certificate causing the problem was installed, but completely unrelated and not actually the one I was using to configure my Hybrid Exchange environment.
It seems this is a known bug and was fixed in Update Rollup 1 for Exchange Server 2010 Service Pack 2. I can confirm that after installing the update, it all worked as expected.
For more info and to download Update Rollup 1 for Exchange Server 2010 Service Pack 2, click here