Supongo que su menú no es creación 100% propia, sino que es algún ejemplo que ha adaptado a sus necesidades.
De no ser así, disculpas por mi presunción.
Debería verificar que no ha omitido nada, ni del html ni del css, del ejemplo. Porque los códigos que ha publicado no funcionarán nunca en ie6 debido entre otras cosas a que ese engendro no acepta la pseudoclase /:hover/ más que en los enlaces /a/ y en su html las listas /ul/ de segundo nivel quedan fuera (como debe ser) de los enlaces.
También deberá repasar los selectores css. En un vistazo rápido he visto que separa con un espacio en blanco el /:hover/ del enlace:
Cita: .menu :hover ul :hover {} /*<-- erróneo*/
.menu:hover ul:hover {}