I use a similar method, but I try to do a general rough brush layout for the majority of the map first, then go back to fill in the rooms, but so far it doesn't work too well. The reason I say that is because I often go back to areas I already roughed out and decide that the layout doesn't work or there's something else I want to do with that area, so I end up demolishing a lot of what I already built to put up something new. (I did this on my first map, and it shows.)

I'm not really happy with the layout my map has now using this technique, and a lot of my other maps have turned out subpar with this as well. I would quit working on it, but I've already spent a large amount of effort trying to fix it (which isn't happening.)

For the next map I plan on making, I'm trying to map it out on paper first, but I find I have the same problem you do and end up thinking of it as a Doom2 map and tend to neglect the Z-Axis.

Whatever I decide to do on my next map, I definitely have to be careful. I'm doing lots of testmaps to get architecture/styles/techniques down in the editor so that when I do start to work on it, I'll have a general idea of what I'll be putting into my map. 

And I seem to be better at it than some other aspects (e.g. consistency of theme and overall look, detailing), or at least it seems more fun to me, and not as much like work. :)

I pretty much use the approach Zwiffle talked about; I build the entire map with broad strokes and using about 3-4 textures--no details at all, then do a shitload of playtesting and just running around the map to see how the movement and flow feels. Then there's a second phase of tweaking connectivity, either altering slightly what's already there, or (often) adding new connections between rooms and areas, and sealing off old ones, to further enhance the flow. Once you get the map compiled, and start noclipping, you can start seeing opportunities to make layout and connectivity *much* more interesting, and make the z-axis really shine.

Zwiffle, why is it a bad thing that you end up demolishing roughed-out stuff to make something better? That's kind of the idea. Or is the problem that it isn't necessarily better? Not sure if I'm understanding you... 

I usually think out the theme before hand - what the place will be, the general range of textures I'll use. If it's more than 1 floor, I draw in seperate areas of the grid paper, or seperate sheets - the floorplan layout of the rooms, where they connect, where stairs are and other notes like liquids, ladders, windows - then begin building it in 3D. Usually I work one room at a time - I build the entire room from first brush to final, decorative brush(es) - instead of making the WHOLE level frame and then adding - because then it gets overwhelming.

Either way I suck at layout design, which is why I don't map. 

How do you create the layout of the map you are building?

Have you ever looked in the toilet bowl before flushing? 

When I put in the inital rooms, I don't think at all about the details I would put into other rooms to try and give the map a unified feeling, and when I re-do areas nothing seems to fit correctly.

I like to have things uniformly scaled and orderly, but I'll end up having, for example, a wall detail in one room at a certain length/scale/whatever, then when I try to implement it into another area it won't fit at all. Then I have to try to make it fit without seeming totally disproportionate (spelling????), but it usually does not work at all, and I get frustrated and just take it out.

I have problems like this all the time. Even when I make sure that something would fit correctly, somehow I manage to screw it up. So then I think it probably would be cooler to make it off-scale or something, but that doesn't work either.

Some main problems I have with layout is centerpieces/central areas, and making a good interwoven layout. I tend to make linear maps with little to no backtracking, which I've read improves the map a lot by
1) Making it seem more like a real place
2) Lengthening the map without taking up a lot of extra time to make more areas.

Oh, and also making the layout interesting is difficult as well. 

nowadays, i tend to meticulously plan out the layout of my maps before even laying down one brush.

my latest map is certainly being built this way.

first, i draw a rough sketch of where the main areas will be, with simple corridors, boxes, etc. this version is expressly for working out the general gameplay. ie: a room intended for horde combat will have "Lots of Monsters" denoted in it, whereas an area with a more specific monster attack would have a little paragraph explaining what it should be, ie: "When player passes through arch, door opens, ogre jumps down behind the player." or "spawn two vores and have some fiends distract the player" or somesuch.

next, i redraw the the whole thing (or each part if it is a large map) this time with more detail attention to the actual walls of the map. i add in specific angles or curves to the walls that i think would look good. i try to imagine the map in my mind, and then i mark down areas which would benefit from "cooler" brushwork, or setpieces... ie: "Fancy Crap" with an arrow pointing to a wall.

Finally, i look at the places that are going to be the more complex ones and i draw them all in perpective 3d, trying to flesh out the actual look of the place.
i find this step helps a lot with theme consistency because it takes a fraction of the time it would take to actually build the areas.

also, note that when i am actually building the map, i do not follow my plans rigidly. if i think of something cooler, or have a flash of inspiration, i'll do that, and leave it hanging in the void until i find a way to connect it with the rest of the map. 

when i'm trying to *find* the feel a map should have, i'll just sketch out bits of archtecture and see what i come up with. 

Before starting anything: I put the global layout "on paper"... It gives me more or less a good idea about the map... Further ideas will come later, during mapping...
Then, starting form the paper, I start mapping room after room, etc...
Basic method in fact...