I'm not so good with critique or communication but I'll try and say what I think doesn't look so good.

The shades of grey you're using don't look so nice, try adding a bit of colour to it (bengoshia has shown this in an edit too). Especially in the white spots of the mushroom.

You could also benefit from some more interesting colours or hue shifting, the mushroom purples and the red enemy stand out for me there. There's also a lot of ugly banding like around the mushroom mouth and soldier guy's head.

For your sword animation, it looks a little strange and clumsy, almost like he's swinging a fish instead of a deadly sword. I got some good advice on animation in a topic of mine who explain it better than me: http://www.wayofthepixel.net/pixelation/index.php?topic=9837.0

Why do you only have a black outline on the top half?

-

Thought I'd flex my nerd muscles by mentioning that "Shatterhand" is a westernized port of a Japanese game called "Tokkyuu Shirei Solbrain", which in turn is based on a TV Show about robot cops or something.

Incorrect.

I used the site Game Kommander for that information, which is far more reliable that Wikipedia.

http://www.ne.jp/asahi/hzk/kommander/rvsrs.html

From what I can tell it calls Shatterhand the original, and says Bandai made them update it to include one of their licenses for the Japanese release.

http://forum.insomnia.ac/viewtopic.php?t=3096

Laziness with animation is horrible.