Completely agreed with lief.
Art related;
I think it would be nice if you added a tad more detail to what you already have, but not so much that it detracts from the style. Like some bones sparsely placed throughout the ground, or a cloud or two more in the sky above Mr. Red to make the sky more consistent, because right now it looks like the sky goes from crystal clear to densely dotted with clouds.
I also agree that the red guy is a bit too red. Perhaps a little downtoning the brightness...?
Lastly, perhaps it's just me, but that pixel-thin twig in the tree is...odd...
Not art related;
For a game, I picture this being like
Lenny Loosejocks in Space, but without infinite lives or health, and controlled with the keyboard. There'd also be some battles akin to Megaman, Mario, or Sonic, but only maybe one to four. Just a short game. The animations would be fluid and pretty, with many small details such as the stars sparkling in the sky, those little creepy shadow guys popping up/hiding and blinking, and the water havin' a nice anim to it. Mostly, it'd be based on simple puzzles, item collectage, and reflexes. Controls would be walk/run, jump/climb, pick up/use/push, and shoot. The shot would be just a short ranged stun gun, used more strategically than run 'n gunnerly.
Maybe the innocent looking critters could be pixels, and as you go along, you gain appendages and stuff - going from a simple square to an armed, bipedal redman. Your task could be to lead the blue innocents to a safer land while keeping as many as possible. They'd have six simple commands; Stay all, Follow all, Attack all (select target), Attack single (Ditto), Follow single (The nearest will come while all others stay put), and Stay single (yup). But, of course, there would be places that only you could go and then open a passage for them to come to you through or make a bridge or something similar.
Man, I wish you could program.