Hey Rob,
Here is what I'm thinking. This first drawing is a rough schematic for just the crosspoint section of pins. Other pins could be added to these and all the rest of the pins would need to be passed through 74LVC16245's as well.
Red trace is on bottom
Blue is on top
Black is on bottom (5v, 3.3v, gnd)
To answer you question about the pins, Mayhew Labs came up with a pretty nice solution.
http://dl.dropbox.com/u/55783756/Photos/go_between_shield_front%20(1).jpg
http://dl.dropbox.com/u/55783756/Photos/go_between_shield_back%20(1).jpg
As you can see, the headers don't go through the pcb, but are instead surface mounted. This way, we could have separate top and bottom circuits.
Dan