What exactly is "bad" about them? I think this calls for sample data.

There is only so much you can do with a handful of pixels, but it will probably help if you scale it by a power of 2 so that the new pixels line up exactly with the old ones.

PS: You aren't using JPG for the intermediate steps I hope! Keep the originals and temp files in a non-lossy format and only convert to JPG while you are uploading/burning them to the final destination.