Alcune considerazioni:
Quando c'e` display: none;, lo z-index non ha significato; prova ad inserire lo z-index corretto quando dichiari display:block;

Non dichiari z-index nel primo menu (quello sempre aperto): questo potrebbe trarre in inganno qualche browser.

Utilizzi la pseudolcasse :hover su un[*]: questo non e` riconosciuto da IE (:hover funziona solo in un <a> o <area>)

Il codice HTML non e` corretto (mancano alcuni tag di chiusura - ma forse e` opera dei tagli che hai fatto).

In caso di piu` di due livelli, avrai bisogno di tre livelli di z-index: ti consiglierei di usare numeri comodi e (relativamente) piccoli, tipo 10, 20, 30, ...

Quando fai le modifiche fanne una alla volta, e verifica di volta in volta.
Poi facci sapere.