The "squares" pattern is quite visible at 100% pixel-for-pixel zoom, even outside of paint.NET in a browser, using this second test image I posted previously above:
http://forums.getpaint.net/uploads/monthly_01_2014/post-134862-0-38051500-1389670699.png
So it is not a problem with any resizing algorithm in Paint.NET or elsewhere.
To reproduce in Paint.NET v3.5.11, start with an 800x600 canvas, fill with black, then go to Effects->Noise->Add Noise. Choose intensity = 64, saturation = 100, coverage = 100.
I haven't tried on another machine yet, but it certainly looks like you