Are you sure it's not just a matter of being in the desert? While there is a possibility of an error with traits for generals, captains should never be affected by any movement traits or script.

But you may have had a flood, perhaps? That usually permanently bugs the movement in that province, and it's a vanilla RTW bug. You may be able to correct it by starting the game, then alt-tabbing out to delete or rename EB/data/world/maps/base/map.rwm, and finally loading your campaign. If this doesn't help, and it's only reported to work in a few cases, there is nothing you can do except playing on with reduced movement in that province or start a new campaign.