I stripped a classic n64 game map/level and only the landscape remains. I need to redo the whole thing in super HD so the original mesh just won't do. I'm having a hard time thinking of a way to get the general shapes and layouts correct. Should I bring the original map into mudbox/zbrush and use a separate plane to sculpt "over" the original mesh and separate them? Is there a better way to approach this?

I would honestly literally sculpt the original mesh. Why sculpt over it with a separate plane, when you could just... add the additional geometry straight onto the original, using it as a base?
I only know where to start on this in Zbrush and don't know if Mudbox has a similar function, but I'd use dynamesh to add enough geometry to sculpt on and even out the existing geometry, then just start sculpting in the terrain.

Edit: Though I'd probably duplicate it first, and hide the double. Just so I have something to reference to make sure I'm not going too crazy.

The mesh is so broken that I don't know if it's useable as is. That's why I wanted to sculpt a separate plain over it to get the same general shape. I need to expand the middle part as well which complicates things.

Thats why I suggested it, Dynamesh is seriously the the most likely easy answer to your problems. It just... retopo's the entire mesh so that it's even quads. I'd use your modelling software of choice to expand the middle part however you can get it to work (barring the use of ngons, of course), then import it into Zbrush if you can. It looks usable (for that purpose).

If you really don't even want to/can't try this (no access to zbrush, for example), then yes, using a separate plane on a new layer and sculpting over the top of the old map will work pretty well.