Every install I was getting 'Error 1603'. After many attempts to install with different fixes (From editing permissions, to reinstalling .NET, and more), I found my main problem was that my OS is x64 and Paint.NET was trying to install as x86. I got the error "32-bit MSI may not be installed on 64-bit OS." inside my 'pdnMsiInstall.log' file in my %Temp% folder.
My solution was to open a Command Prompt and ran: paint.net.4.0.5.install.exe /createMsi
(Which I found from http://www.getpaint.net/doc/latest/UnattendedInstallation.html)
This will create two MSI packages in a folder on your desktop called PaintDotNetMsi. These MSIs are each targeted at a specific OS/CPU platform type (x86 or x64). These may be deployed via standard AD/GPO mechanisms, and are already patched with the MSI properties that you specify using the PROPERTY=VALUE command-line options (if any).
It created 'PaintDotNet_x86' and 'PaintDotNet_x64' in the 'PaintDotNetMsi' folder on my Desktop. I was then able to run 'PaintDotNet_x64' (As I said, I'm x64) and it auto-installed and is working great.
Side Note: I was able to install Paint.NET.3.5.11 (A file I found on an alt site) without any issues.
08/12/15 Edit: I again ran into the issue of updating to 4.0.6, I again did the /createMSI trick and was able to install with no issues.