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.