I've been having the 1603 problem and just couldn't get Paint.Net to update itself.
This morning my iTunes also refused to update itself. Looking into the problem, I did the following:
Goto:
1. C:\Users\xxx\AppData\Roaming\Microsoft\Crypto\RSA
2. Delete the content in the above location.
If in doubt, move the contents somewhere else.
Afterwards, both Paint.Net and iTunes installed.