I really like the changes on this I Am Uh, you can really see a ton of improvement.

I do think though that you could do with some contrast in this, I've tried to do this by altering each colour individually, trying to not keep the saturation too high but it's very tricky as you want forms to read well yet your character to not get lost by high contrasing tiles. Hopefully I've hit between what im trying to suggest with this edit.

First I worked on the rocks, sharing the darker brown from the enterance and introducing a black I'd think you'd be best making sure some you have a more shadowed side and a lighter side so we can determain some shape, otherwise we could suggest it's just a flat road or something, as the grass doesn't change at various levels.
Tried to increase the colour of the grass and water so everything is more or less consistant, keeping in mind whether a character would get lost or not against the backdrop.
That thing attached to the rocks along side the entrance, not too sure what it is, but I think some colours are wasted here, made a slight suggestion. take it or leave it, don't know what I was pixelling.

Oh I'd always check your character on your mockups whilst working on backdrops to see if they work together, because personally I think he seems too seperated on your version. You need to have a sense of solid objects, and clear paths. Otherwise things can just seem confusing, plus if everything just 'fits' together with great consistancy it can help make a game just nicer to play.

well judge for yourself, hope any of that helped.

-EDIT!-
where does grass ever just grow up to and then into the sea? I'd understand if theres like a drop (where grass grows to the end of a small cliff or something) but this appears on the same level as the water and even seems to be growing into it. I'd expect some sand or dirt somewhere.

But ah well it could work.
Here's my effort to collect some examples of stuff here on pixelation and pixeljoint to possibly help.
http://img.photobucket.com/albums/v294/Frog32/terranigma1.png - Josiah Tobin
http://www.imageuploads.net/ims/pic.php?u=12254DDjsy&i=92899 - eghost
http://img.photobucket.com/albums/v133/Timpac/Rewerk.png - Doppleganger's edit to Tsugumo's work with some excellent critique http://www.wayofthepixel.net/pixelation/index.php?topic=3557.msg44832#msg44832
http://img201.imageshack.us/img201/6687/zmockwr8.png - Stranger
http://i22.photobucket.com/albums/b340/baybaybom/sab-liftr3.png - within conceit's list of pixel art he likes
http://img135.imageshack.us/img135/6015/difftree5lv.png http://img147.imageshack.us/img147/1696/mock6ex.png - .TakaM his threads also a good read http://www.wayofthepixel.net/pixelation/index.php?topic=1470.msg18568#msg18568
(In fact also a good read from .TakaM http://www.wayofthepixel.net/pixelation/index.php?topic=1668.msg20694#msg20694)
http://www.crystaltechstudios.com/projects/Legacy/Legacy_Mockup_2.gif - Dhaos
http://pixeljoint.com/pixelart/27489.htm - Doppleganger
http://pixeljoint.com/pixelart/11203.htm - vedsten
http://pixeljoint.com/pixelart/15423.htm - Scruffs
http://pixeljoint.com/pixelart/26729.htm - born
hope it helps. 