Canna, I don't know why this 1603 error happens for some people. I have uninstalled, installed, and updated Paint.NET thousands of times and never had this problem.
However, for this specific fix, the problem has nothing to do with Paint.NET. A system file became corrupt and there are ways to fix it (I recommend using SFC, and not downloading a random version from some website). Paint.NET cannot be blamed for that.
For me this was not true. It had nothing to do with the system but obviously with some paint.net registry values.
The problem occured for me when I installed Paint.net v.3.5.5 on a drive other than my System drive (Windows 7). I had some problems with my Vista boot which was on that partition and long story's short, the program data of paint.net(and some other programs I installed under Windows 7) got corrupted.
I was forced to uninstall all the programs on this partition and for most this was no problem. The uninstaller of Bad Company 2, Skype, VLC worked with no problem but I was unable to uninstall Paint.net (stated that a program needed for uninstallation is not running properly) neither could I install it over the old installation due to this 1603 error.
I tried SFC.exe which found no errors in my system (no wonder the installation is brand new), I cleand the registry with CCleaner and removed all files from the trash.. Nothing helped.
Now I finally was able to install it properly, this is what I did:
1. Uninstall the Program via Add/Remove Programs (it won't work but remove the program from the list)
2. Use Ccleaner to clean your registry
3. Move to "C:\Users\MyUsername\AppData(Hidden)\Local\Temp" and delete everything in it
4. Open CMD:Regedt32
5. Search for "Paint.net" and delete all entries for paint.net (you can leave those associated with filetypes like png, or jpeg). You will find some references for temp-files, dll's, exe's and a cryptic Windows installer folder consisting only of numbers and letters.
Then run the installation and it should succeed..
However, as always there's no guarantee this will work and
you could seriously damage your system if you mess with the registry...
But I think the problem lies within the temporary files, or references to those, which cannot be overwritten or something.. I believe that the PdN installer messes something up..
Could be the reg keys:
[HKEY_CURRENT_USER\Software\Microsoft\Windows NT\CurrentVersion\AppCompatFlags\Compatibility Assistant\Persisted]
"C:\\Users\\USER\\AppData\\Local\\Temp\\Temp1_Paint.NET.3.5.5.Install.zip\\Paint.NET.3.5.5.Install.exe"=dword:00000001
[...]
"D:\\Programme Win7\\Staging\\Paint.NET.3.5.5.Install.exe"=dword:00000001
Or a bunch of keys looked similar to this ones(tons of file references which are, of course, no longer existing once they are deleted)
[HKEY_LOCAL_MACHINE\SOFTWARE\Classes\Installer\Assemblies\D:|Programme Win7|Paint.net|ICSharpCode.SharpZipLib.dll]
Long story's short: I'm glad I could fix everything and it is working as intended now..