Hi, did you find a solution to your problem ? I have the exact same problem.  The only difference is that I have a single X509 certificate which has a public and private key.  I also can encrypt without problem and I get the same error message upon decryption.

It might be a stupid problem, but without proper documentation from Microsoft, it's hard to solve.  Cryptography is easily the worst documented part of the .NET framework.  It's a real shame.