Thanks for the input guys, I really appreciate it!

I know my greens aren't greens, but they look green lol.  Cool edits Sardone!  It's neat seeing style choices I wouldn't have thought of on my little dudes.  Comparing yours to the originals made me notice a few issues I had with AA, and some areas on the characters that weren't very readable.  Glak described what I'm going for almost perfectly.  I don't want to oversaturate everything and completely change the "feel" of what I have going here.

Right now I'm jumping between my sketchbook and my laptop, trying to simultaneously design these characters by hand and trying to translate them to pixel as I go along.  You guys are both right though, I should start pumping out some background tile ideas.  Thanks!

I have to do a take on the story, all the ideas are brilliant!


(cut and pasting the beginning here)
You're a young boy, living in a house on the edge of a village.
You wake up one night to a loud thump and bright lights outside your room (think alien abduction movies), you look out your window but you can't distinguish anything, so you go back to bed.
You wake up the next morning and look out your window to see a bunch of really buff men, glistening shirtless or in overalls, digging a big hole in your backyard. (this may go on for a few days or may not, i haven't decided) But you eventually go out there to confront them and see them all jump down the hole. You go over to look into the hole, but trip and fall in, landing at the bottom of a really deep pit unconscious.

The boy eventually meets a elderly blind man, digging to China.  He logs having met you in his journal.
The boy also meets a band, but are separated when the ground shakes and a mining machine digs through the ground.  The boy and the band don't come across each other throughout the game again.  Peppered throughout the game where the boy gets into some deep trouble with the Buff Men and their mining machines are cutscenes showing the band's progress exploring the caves.  Some silly events always lead them to jam out on a new tune which becomes (gasp) the boss music!
BOSS FITE GO
The Buff Men suffer defeat every time, and the boy resumes exploring.  Rinse and repeat.

At the end of the game the boy finds where the Buff Men have been digging to, a massive deposit of SOME DIRT I GUESS!  The boy is spotted by a bunch of Buff Men and they combine to form the Buffest Man!  At that exact moment, the band crash through the ceiling and see that kid being bullied by the Buffest Man, so they help out the only way they know how, by performing an awesome live boss tune.
FINAL BOSS FITE GO
The final boss fight involves somehow having to hit a part of their super huge mining machine to spray them apart with some sort of valves on the machine.

It turns out the Buff Men are an alien species looking for a specific source of mineral that makes fantastic protein shakes, which can only be found underground in the boy's backyard.  The reason why they were in a fury the whole time is because they were really, really thirsty, which was soothed by all the protein shake the boy gave them.
The boy is okay with this, and forgives them.  Cue credits and cutscene where all the Buff Men, the boy, and the band are rocking out, dancing, and drinking awesome protein shakes.

EPILOGUE
The Buff Men give the boy and the band a ride to the surface and after goodbyes, zoom off into space carrying a full load of protein shakes.  The boy and the band also part ways and the boy returns home, just in time for supper.

A Buff Manian digging machine emerges from the ground in China.  The machine's door opens, and the elderly blind man emerges.  He made it.

THE END


I know it's nothing at all like what you had in mind, but maybe having silly throwaway ideas would help.  That's what I do, I always come up with assets before building a story around them too.  I find just having weird ideas to play with usually inspires something usable sometimes.  Hope I helped at all!