I'm getting that error too. It seems to be the same error as in viewtopic.php?f=10&t=21585&p=122008 , and I also tried each step in the sticky. I never had Paint.net on this computer before and I have full administration priviledges. It seems that this error occures only for the last few versions of pdn.
Anyone got an idea?
edit: I installed v 3.10 without any errors. But if I try to update, I still get that error #1603/1722.
It seems that you've included an prerequisite which causes errors on some systems.