Comment 1 for bug 205299

I think this is because the upscaling algorithm used is GDK_INTERP_NEAREST which is not that good.
(documentation: http://library.gnome.org/devel/gdk-pixbuf/stable/gdk-pixbuf-scaling.html#GDK-INTERP-BILINEAR--CAPS)

I tested instead with GDK_INTERP_BILINEAR and I find the result pretty good with (I think) an acceptable penalty.
I did a comparison on my AMD Athlon 64 5000+ containing 83 nds roms to know how much more CPU it costs compared to the original code:
upscale to 64 pixels penalty : 12.93103448275862068900 %
upscale to 100 pixels penalty : 29.10052910052910052900 %
upscale to 128 pixels penalty : 34.61538461538461538400 %
upscale to 192 pixels penalty : 46.18395303326810176100 %
upscale to 200 pixels penalty : 47.43362831858407079600 %

The change is in: "gnome-nds-thumbnailer.c" line 186 of 198
change
scaled = gdk_pixbuf_scale_simple (pixbuf, output_size, output_size, 0);
by
scaled = gdk_pixbuf_scale_simple (pixbuf, output_size, output_size, GDK_INTERP_BILINEAR);