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