(Nearest Neighbor produced identical results)

Sorry, then whatever software you're using to scale it is broken. The image pictured is obviously nearest neighbor; rescale with bicubic and it will look smooth but blurry.