I found the solution here:
I had to give my user account access to the key container in C:\Documents and Settings\All Users\Application Data\Microsoft\Crypto\RSA\MachineKeys. It turns out, even administrator rights were disabled on my machine! I am not sure if this was the default installation (I rebuilt the machine a few weeks ago) or if this is modified when I install WinFX, or if when I granted ASP.NET and NETWORK SERVICE access it somehow lost the inherited permissions that were granted when I installed the OS. In any case, at least it seems predictable, you need access to the key store in order to generate keys, makes sense!