As a bit of backing, I've been using a palette Arne used for his gameboy mockup here quite a while ago to work on a 4 colour, gameboy resolution game (without spriting restrictions beyond 1 bit alpha) in Flash.
The most recent mockup:

This is working on 5 layers:
-Foreground decor - the grass mostly, but anything in front of the terrain tiles goes here (so large underground flavour decorations might go here later.)
-Foreground tiles - what it says on the tin. 10x10 tiles on an 8x8 grid, so 1 pixel of overlap. Rendered left to right, top to bottom. I'm only making use of the overlap on the top of each tile, for things like the rocky surfaces.
-Objects - everything that does anything interesting. The player, mines, crate, fence, all of these are objects, and some are animated.
-Background decor - mostly vegetation but also the road sign.
-Background tiles - currently only the cave tiles, this will likely include pipes and buildings later on, unless I make them out of decor.
The HUD is still entirely work in progress, I've only started mapping out the elements now. I'm unsure of whether to go for mixed width 6 high gliphs (including shadow) or fix the size at 6x6 per gliph for monospacing. I've never been able to get a 4 pixel wide M or W to work, and it'll be even harder with only 4 colours to work with because of the lack of any multi-colour AA trickery. That said I'm interested in your suggestions here.
I'm aiming to keep content production time as low as possible on this title, but I also want it to feel polished. I figured you guys would be able to identify all the clustering and banding issues a lot better than I could.
As a note, I'm fully aware of the banding of the mine lights (most notable on the underground landmine to the right and below the centre of the piece) but I need the sprites for all objects to be compatible with light and dark backgrounds so I've resorted to outlining on the full light and full dark elements. Alternative solutions are also welcome.
I'll post some of the animations soon, I've got to run now and I'm hungry for some feedback.