It could make labor migration much easier-- it would be happening anyways, people from less agriculturally productive regions need money and people from more productive regions need labor (but specifically laborers who won't settle permanently, less people you need to share this soil with the better). Peddlers would also find their lives made easier by two wheeled or three wheeled pedal-power vehicles with loading platforms on the back. And army maneuvers-- bicycles helped make the Japanese attack on British Malaya even faster. However, those Japanese soldiers weren't decked out in full plate-- might be that infantrymen would have to give up some of their armor, unless that's being made out of lightweight metals as well.
However in the end it's still human power, people might go faster but they need the energy to do so. Inns, good roads, bridges-- and more importantly, the who administer and charge tolls on those-- are going to be the necessary other half of the transportation picture. Easier transport may mean that different realms police their frontiers more, not necessarily to keep people from getting in but to keep them from going out-- which could finally culminate in a retrenchment of serfdom and abolition of the bicycle as a threat to public order!
