To expand the previous answers, if you search the fotf threads for the map rewrite, there's a number of problems relating to the main issue of DF having z-levels, but the worldgen mostly seeing those z-levels as completely separate. These problems include... :
1. Underground travel is not just hard for the player adventurer, but also for the AI, to the point that this is the main reason megabeasts teleport to your fort. Forgotten Beasts in particular just can't navigate the underground caverns.
2. 3d veins, underground rivers and other 3d geological features (better volcanos for instance) are really difficult to code right now.
3. Dwarf forts are really hard to generate properly, forts often generating without an access, and placement of rooms being very flakey.
4. The overlap of features being really bad. My adventurers have visited a number of hamlets which overlapped with volcanos in rather disastrous ways.
The mythgen itself also has certain needs. For example, if the mythgen says that there is a huge tree in the center of the world where all living creatures came from, DF currently isn't really capable of generating that tree. Other things mentioned here are seperate planes, like the afterlife, or having the worlds themselves be 3d, like consisting of several chained up cubes.
On top of that, magic and gods kinda aren't that impressive without natural disasters, so volcano eruptions, typhoons, tsunamis, meteors crashing down, and all that requires both the worldmap and the playmap to be able to handle changes. This also ties in with the idea of floating continents and moving fortress sections.
So, right now the idea is to change the way the game thinks about z-levels and the placement of features (which will also bring some other possibilities like being able to see outside the current game map), but the thing is that this happens like a thousand times over the whole code. So it's a very boring thing to do that also won't really show the results of it without a ton of extra work.
I remember the world activation release was received really poorly as all people could see was sieges being bugged, but now we've got the new civ screen, travelers and villains it is much more obvious what that initial release was setting up for. So it makes sense to me when Toady indicates he wants to integrate mythgen, do the map rewrite and at the least one or two things that obviously cannot be done in the current DF (I think the primary candidate is floating continents) and have them all in one single release cycle.