I considered suggesting steps on the cane earlier and i think that you can do it without actually changing the speed the sprite moves if you have the whole body slide backwards on the frames when just the cane advances. I'd edit to demonstrate but I'm pressed for time. Reply if clarity is lacking.
Some people use a cane who are perfectly capable of walking without it. Some people need it only for stairs or bending over. Some people advance the cane with the step (leg+cane, leg, leg+cane), while others must wait and advance the cane alone (leg, leg, cane). Some people must advance the cane on every step (leg, cane, leg, cane). The level of mobility will impact the way the character is perceived.
Ben gives a brilliant edit on the spine movement. There's a tremendous difference between not moving much and not moving at all. Also look at the way he's animating less active portions like the head position, utilizing circular motion paths (a fairly advanced skill) brilliantly in that they allow him to move tiny distances in more frames, smoothing out motion without significantly increasing the range and also without increasing the jerkiness. It also presents a great method for finding movement. Also look closely at what he's doing with his smaller motions - the significance of the head movement on the 'limp' step allows him to put greater movement on the 'steady' step while having it still appear understated and level because of the comparison. That is a prime example of how one aspect considers the whole in a way that can't be figured when working in tiny modulars, not just across space but across time.
That video is a great find because it's an example of someone putting incredible, visible effort into keeping his body stable at high speed. You'll notice that he's waving mostly with his lower arm, reducing at the elbow and locking the shoulder action into a tight rotation, minimizing lateral shift. It's a little funny actually since stopping his shoulder action (which actually robs him of all the momentum built by pumping one's arms... his body is begging to move more and he's not allowing it. Still, his torso and shoulders are moving a lot within a small space, and that's still very different from not moving.
In general, when running the shoulders move in circles, which oppose each other. The shoulder opposite the stepping leg would be swinging up with the arm, generating forward power, while the other shoulder falls back high and then scoops in to advance and swing up next. Shoulders also tend to rotate around the y axis. Good shoulder movement is important because it does a number of things. The pumping directly generates momentum forward on the shoulders which pull the spine and the hips and gives greater movement during suspension, the most important time of the run because the body is not able to apply force to the ground in order to maintain or increase speed. The twist also works against the hips to make both actions - pumping and stepping - springier and stronger. Torsion is among the strongest and most violent natural forces. Last, it actually compresses the diaphragm, which facilitates deep breathing. If you relax your core, work your arms properly and open your airways, you should actually find yourself taking shallow, unconscious breaths.
As for the spine, top-speed is achieved when the spine is able to hop forward and then straighten as though it was a jumping stick. This further builds momentum and is assisted by the movement of the shoulders. At the moment of passing (or really just after), the spine should be almost perfectly straight down the receding leg.
If you have all these motions, even fast and small, your run will gain life, smoothness and believability. Unfortunately because they are small and interconnected, they are terribly terribly difficult to add into a finished run. Moving around chunks of finished animation a piece at a time can't reflect such subtleties, it demands close attention no matter when you address it. This means either planning it the fist time, or doing as much or more work later when you go back, and that's a direct, practical reason that for this thread in particular I urge the methods I've discussed.
