The new background looks good, you can really see what you want to focus on now. The purple tint is good, it makes the colors almost fully complimentary.
Despite how similar others say the tiles are to cavestory, I think they have their own thing, but the blocks stuck in front of the more natural looking foreground...that seems pretty signature Cave Story/whatever other game to me. Try sticking them behind the rock tiles! I bet that'd look much more natural.
:C Level editing in MS paint, I sympathize with ya, hooh.
Another thing, I recommend toning down the highlights on the pillars, just to make them more background-like.