So I recently finally figured out the woe to one of my most plaguing issues when I do video editing on my computer. Adobe premiere has an incredibly nasty habit of just deleting the transparency of images it handles as if they never had it to begin with. I've searched for the solution for months and finally found the culprit tonight.
As it turns out, premiere eats the transparency of any images saved in index color modes, and as it happens almost everything paint.net touches ends
In the PNG save configuration dialog change the Bit Depth option from Auto-detect to 32-bit (or 24-bit).
The Auto-detect option picks the PNG format that produces the smallest file size, which in your case is one of the indexed formats.
The Indexed PNG formats do not support semi-transparent colors, so any images that have them will be saved as 32-bit RGBA.