I think the sprite is pretty nice. The Selout is too prominent though. Either lessen it, or get rid of it all together.
The main isue is the walk animation. It doesn't work. At all.
However, lucky for you, our big bad pal Ptoing just made a nice breakdown of a run animation in another recent thread:
http://www.wayofthepixel.net/pixelation/index.php?topic=6233.msg73689#msg73689Take a look at it.
A walk animation basicly exists out of 4 key frames per side. So 8 in total per cycle.
The contact, the recoil, the passing and the high point.
In Ptoing's picture the 'extreme's' are basicly the high points in the animations. The kind of highest, furthest stretched point in the walk cycle.
The contact comes directly after the high point, and the passing directly before the high point.
With inbetween, the recoil.
I don't know if this actually is a normal way of aproaching this, it helps me out atleast.
Once you have all these, you can make more betweens, to smoothen out the walk animation.
Remember though, depending on your image speed you may not want to make it too smooth.
A thing that I think has alot to do with wy it looks wrong is that he nearly seems to be flying.
His legs spend far too much time in the air. Remember that when walking or running, you're pushing the ground away to propell yourself forward.
You're not trying to swim in the air

Something that can also help give your guy some character, is to turn his head a small bit when walking. Or making it woble up and down a bit.
Often it helps to just really look at yourself.
In the mirror, or just normally. Take a walk and see how each leg and arm moves when you take steps.
The walk animation aside again, is this a boy or a girl?
Not because of his face, which seems manly. But it's his shorts, which seems to react like a skirt.
That's about as much as I know of it, anyway. Hope it's some help, haha.
Here's a bit of an edit like example thing I cooked up.

It's quick and sloppy. But hopefuly gives you an idea?