So, the problem went away at some point (I think as Swidden was starting?) My best guess is that it has something to do with the game thinking I'm still slowed by the snow, even though there is no snow on the ground?
(I even tried skiing even though there was no snow, and of course it did not let me).