It's all about how the compression settings are used (or misused, in some cases).
Photoshop is notorious for its bloated PNG output. Paint.NET simply correctly takes advantage of the compression built into the PNG spec.
There's also the possibility that other metadata may be saved into the file, resulting in size differences.
OptiPNG could probably make either file smaller. In fact, I think there's an OptiPNG Plugin for Paint.NET. (Found It!)
Some versions of Adobe Photoshop, CorelDRAW and MS Paint provide poor PNG compression effort, further fueling the idea that PNG is larger than GIF. Many graphics programs (such as Apple's Preview software) save PNGs with large amounts of metadata and color-correction data that are generally unnecessary for Web viewing. Unoptimized PNG files from Adobe Fireworks are also notorious for this since they contain options to make the image editable in supported editors. Also CorelDRAW (at least version 11) sometimes produces PNGs which cannot be opened by Internet Explorer (versions 6–8).
Adobe Photoshop's performance on PNG files has improved in the CS Suite when using the Save For Web feature (which also allows explicit PNG/8 use).