IMO, the biggest problem with multiplayer with the game as it currently is, is the asynchronicity. Can be largely avoided when running separate parallel fortresses (or Adventuring in totally different parts of the world), but particularly hard to imagine being handled very well when group-Adventuring and having fortress sites with intimately touching (if not overlapping) areas of influence.
What are we going to do when one Adventurer tries to move, move, move over the landscape with rapid taps of a direction key, and the others do nothing (or are checking their inventories, message histories, looking at the global map, etc. And when one player in Fortress mode is busy micromanaging his units, switching job preferences on and off, does that pause everyone else's game at the same time?
There are solutions (e.g. enforced real-time[1], with no actual pausing even while drilling down menus) but there'd necessarily be a drastically altered sense of playing style from now.
Very much suggested, and that indicates a lot of people wanting it, but I worry that it would be game-changing. Yes, a nearly complete re-write would be needed, but not necessarily 'just' to implement multi-threading. There'd be mechanics changes galore.
Of course, such things can be done. Look at how Minecraft servers work (at least comparable to how a multiplayer Adventure Mode would work), although I still have doubts over Fortress Mode multi-player parallelism being practical in any way readily identifiable as essentially the same game-mode (just with more players).
[1] But then you need to make it run at the FPS of the slowest participating machine, to be fair, unless you share out computations so that the legion of participating machines collaboratively tackles everything over the combined area concerned, every tick, the faster machines taking on more work than the slower ones... or a central server, which is much like how the current 'multiplayer' system works.