So I downloaded paint.net V4.0.5 and it worked how it should have but I didn't really like the new features and brush blur and when you zoom the pixels become more blurry at certain zoom levels so I decided to downgrade to V3.5.11, I couldn't find an uninstaller so i just deleted all of the files in the folder containing paint.net and then I cleared the Recycle Bin. I launched the installer for V3.5.11 and went on the custom settings to install it in the folder where I had the newer version and BAM Fatal Error. So then I decided to re install the new version but still... fatal error, I tried to install it in different locations but nothing worked, I looked at many posts but none of them really helped. I haven't created a restore point and I have really important stuff. I went into the windows "uninstall or change a program" clicked uninstall and a pop up appeared saying "there is a problem with this windows installer package. a program required for this install to complete could not run. contact your support personnel or package vendor"
I have windows 8 64bit
Here's What I see
EDIT:
I FIXED IT! After long hours of research and pain I managed to find a program that fixed the problem, My paint.net works now. This is what I used: http://support.microsoft.com/mats/Program_Install_and_Uninstall
If anyone has this problem I hope it fixes it for you!