just to clarify something:
Paint.NET has four ways of Resampling images when resizing .
I assume that you've used the 'Nearest neighbor' option , that option does no smoothing at all , it's used to have the image with all the pixels almost in their places.
if you want the result to be similar to the original , with the most smoothing , 'Best Quality' is your cup of tea :
Here is how the result would look if you use the 'Best Quality' option:
Hope that was helpful..
ps: i prefer your new one xD
Ahmed