Also, that court magician would suddenly find himself in a civil engineering position -
King: You said you could Disentigrate things didn't you?
Wizard: Yes, my leige.
King: Excellent, I have a task for you
Wizard: Yes my leige, whom do you want destroyed?
King: Not whom, what. There is this stretch of land that needs to be perfectly level...
Another thing to take into account is that so far we are using the Roman model, other European models were used that were not even that labor intensive. Many post Imperial roads were little more than horizontal walls without mortar, much cheaper to build. The plank roads (as mentioned earlier were also low-tech solutions to "comfort" problems. Don't forget though that "paved" style roads would be the exception, not the norm (ever hear the phrase King's highway?) and would likely be littered with toll booths to collect toll taxes for the privelage of use. Many times the King's highway would "spawn" several smaller "pauper paths" that would run parallel for those who are less financialy stable.
The King's highway is also a magnet for bandits (leading to the popular term "highway man") which is why nobles would have armed guards accompany them, who would, in turn, complain about the lack of protection on the highway, which would lead to the highering of more guards, which would increase the cost of "maintainance", etc, etc, etc...
Ah, civil engineering class finally "paying" off (sorry about the pun)