I like it, the obvious thing I noticed was, as you said, the palette.. I don't dislike it at all, it just seems to camoflauge the character. I'd just mess around with the Hue/Saturation/Contrast of it.. Also don't settle on a first idea, I'd advice you to keep working on different grass/dirt textures for your tiles you may stumble on something you like better than this. As you said you need help with the dirt, just keep practicing, you basically have the right idea anyway.
This may be irrelevant but I think it helps to see how it'd look if you were actually playing it, I use 'the games factory', it's a program used to make simple games like this, it's very basic so it's just a quick way to experiment with like graphics and testing out character movements.
www.clickteam.com you can download it from their site under retired products in the download section. Also they've release the games factory 2
. it's helping me with my platform tests,
http://img476.imageshack.us/img476/4586/untitledpk5.png.. Though I've still got a lot to do
hope I helped.