It turns out that this is a generic error message that happens whenever the server has trouble decrypting with RSA. Not very helpful, because it is misleading (at worst) and at best, very vague.
For us, the error was only happening for me because our dev servers are load-balanced (which I didn't know till today). The encryption key was generated on one machine (server1) and installed on both servers. When I got load-balanced onto server2, I see this error (so would anyone else on server2).
The solution is to export the private key from server1 and install it onto server2.