Hi Jannew,
I hope I'm not asking a silly question, but are you using the internal updater or have you downloaded pdn from the website and run it independently from the actual programme?
First have a look at http://forums.getpai...-problem/
it seems as though this person had the same issue as you are.
Here are some general fixes to help out if that doesn't work.
If you haven't done so, download the file from the website and try one of these as your problem seems to point to either an unreachable location with your current user access rights or a missing file/corrupt download. Try to right click on the Paint.Net installer and run as administrator.
If that doesn't work try re-registering msi, Start->;run->;cmd(run as admin)->;msiexec /unregister->;msiexec /regserver->;exit. You may need to run cmd as administrator.
Then try installing it.
From your description it sounds as though you have pdn currently installed. One solution maybe to make a backup copy of your current installation and then uninstall it from add/remove programs, then to try installing it from there.
If all of these fail, could you post your log files from start->run->%temp%
PdnMsiInstall.log, PdnSetupNgenInstall.log, PdnSetupShim.log
It will help troubleshoot your issue.