If I may ask, you said you are using Deluxe Paint, right? What are your thoughts on the program? I'm a long-time Photoshop and Gimp user, but both applications have shortcomings when dealing with pixel art, particularly animation and palette work.
In terms of feedback, I really like what a bit of retouching has done to your low resolution version. It looks much more detailed now, while still retaining many of the qualities of the original. I think The woodsy area in the background, the broken pillar in the foreground, and the pile of rubble in particular look much better now. And that dirt-spattered column on the left looks top notch. One smapp gripe is that a few areas still look too soft and show the effects of the scaling.
I'm a fan of the new, more random dithering style. Did you say it started as a pattern dither, then was randomly scattered? Or is it a purely random pattern?