I noticed how Paint.NET is installed...you wrote an MSI package that contains the data, your own UI, and an NSIS-based wrapper, I'm guessing for the compresson.
The installation works, but why do you have, like, three different stub loaders before the users actually see the installer window? Perhaps you don't see what you're missing in NSIS... :?
I have written a new installer entirely in NSIS. It was tested on a computer that had never seen the light of Paint.NET, and it worked seamlessly. It was originally developed for Beta 3, but at the last minute I updated it for 2.5b4.
The full NSIS source code for the installer itself is included, but it was developed using a currently unreleased version of the ExperienceUI and you will need the ExperienceUI version 1.1M2 (currently release pending, but I made it so I can do what I want with it) in order to rebuild the installer.
Download this cool new installer: http://www.freewebtown.com/dandaman32/pdn/PDNSetup-2.5b4.exe
EDIT: This installer is experimental. DO NOT try to just use it if you are new to Paint.NET for now, and by downloading and running this file you are doing so at your own risk!
Until further notice, all updates to this installer will be posted on this thread if needed.
-dandaman32