I couldn't install or uninstall paint.net with any program, or with programs and features
I tried about everything to get rid of error 1603 including Avast, CCleaner... Anyhow I had recently installed windows so I wasn't afraid to try something drastic.
My problem probably resulted when I failed installation and manually tried to delete folders and stuff instead of using programs and features to delete it.
Anyhow I did run: regedt32
Ctrl+F searching for "paint.net" Press "Enter"
Press "Delete" Press "Enter"
I did this over and over again until all results of paint.net were gone Including folders that were obviously associated with the paint.net installer.
Anyhow After deleting everything, I re downloaded paint.net, extracted and express installed it, and it worked.
Don't try but at your own risk... regedt32 isn't to be messed with...