Were you using ALZip to unzip it?
I found another user on this forum who had that problem when I stumbled upon the very same problem. I downloaded ZIP Reader for free and installed it quickly, then the very same download of paint.net unzipped and installed flawlessly.
I have been having the same problem, so I quickly Googled it and found this post. I'm using AlZip too. After downloading a different zip program (ZIP Reader), it worked perfectly. Apparently, AL Zip is the problem.