Thanks for all the comments so far. Here's an update.

I liked the colors in your edit Terley, but I felt they took away some of the brightness I wanted the sky to have. So I compromised, hope it came out alright.

I thought you may want to look at some stuff separately so here's the sprites and the tiles for the ground.





however, i am not too keen on the soldier guy. he looks out of place.
That might be a good thing. The story of the game is about a demon/magic/whatever world in which all sorts of weird creatures live. Criminals of the worst kind in this world is sentenced for exile. This means they get sent to another world (our world). The humans in that world has in their 22:nd century became aware of it and interpreted it as a sort of invasion. They dispatch military units to the magical world to obliterate it.
What is it that makes him look out of place to you?
The ground tiles was the first thing (except Jobel) which I made in the picture and I'm actually not very happy with how they came out. I think I'll have to redo them.