err, Colonel level is +20% move speed... This don't strike me as an insane move speed bonus. A strong one, perhaps but nothing that impossible. Just consider they succeed quite often in forced marching. Plus, the AI has been revised to never get a combat bonus ... Just so you wonder if it has some or not.
Hofstadter's Law: "It always takes longer than you expect, even when you take into account Hofstadter's law."