Maybe you will find this thread helpful

http://www.wayofthepixel.net/pixelation/index.php?topic=3511.0

My tip: you should try to visualize what you want the picture to look like in the end. The way you started shading it (especially the 2nd picture) it is too busy, with small bright and dark splotches all over.
Decide on the lightsource, make the dark and light areas bigger, add some color tints - e.g. make the shadows purplish and the highlights yellowish, maybe add a second layer in the distance to add depth (see http://www.wetcanvas.com/ArtSchool/Landscapes/LearningFromPhotos/Sunsets/Atmospheric/index.html). At some point you may want to clean up the lines.

P.S. Start by doing what M.E. said, color the whole picture first without texturing and shading, use only a few colors (highlights, midtones, shadows). Then once you're happy with this base, you can start adding details.

Thanks a lot for the info, but I decided against hexes in my project since I'd have to change the pathfinding and field of view algorithms. Nice mockup there Adarias, reminds me of advance wars.