For some reason I'm seeing massive travel times on FEI. From Sasat to Nocaneb: 43 hours. No siege engines, troops set to police.
Winter? Bad roads? Wounded troops?
Also: carts? Banners?
If you don't have enough men for all your paraphernalia, it will slow you down, no matter what kind it is.
No paraphernalia. Only 23 men. Even good roads have long times. See image.
(http://i62.tinypic.com/w1rb5x.png)
Worst place to travel in the game. Nocaneb is basically completely isolated from all the regions it connects to, taking ages just to get anywhere. Winter really emphasises this.