I gave this game a shot a while ago, but were quite busy lately, so I didn't post. Didn't get to the second stage, I'll give it another shot soon.
Pretty solid stuff. I like the rogue-like approach to this, makes the game feel much less stale. I think you should consider peppering around a bit more obstacles and items, perhaps some being rarely available - this could make the playthroughs even more varied. Difficulty level will be on spot after you get the platforming more polished.
Graphics are very decent. It's nice that you settled for making original sprites/sounds for this game, this gives it it's own flair. Music needs a bit more work, though - some notes sound off compared to the originals (especially evident in stage start theme), perhaps instruments could've been chosen better too. Some simple tweaks here and there will definitely help it.