The problem with your walk cycle is that there's absolutely no twisting going on with his torso at all. That makes it look like he's flying just about the ground, pretending to run for the fun of it. When people run, they fall (far) forward, before catching themselves just in the nick of time, saving their faces from meeting the ground:
http://www.youtube.com/watch?v=XQEnut04rqU . A runners forward motion is the only thing keeping them upright. If your guy stopped running, he'd be perfectly fine, because he's standing straight up, which is what is ruining the effect.
Your guys arms are also too short; his hands should read about midway down his thighs. Because of this, your smallest guy actually looks the best right now, because he's the closest to being in proportion.
