Yeah, the style is pretty sweet.
The animations, however choppy, fit the NES restrictions, and I agree with the others about the variation in the rock tiles. Work on that a bit.
With the jump, should he do a mid-air roll every time he jumps? Personally playing a game where that happened would distract me. Maybe try a regular jump animation?
Overall, nice, hope to see more.