Otro gran problema !!!
 
Este es mi codigo:  
 Código HTML:
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css">
ul.menu li.primera:hover, ul.menu li.primera.over {background:#FF0000;}
ul.menu li.segunda:hover, ul.menu li.segunda.over {background:#E5E5E5;}
</style>
</head>
<body>
<script type="text/javascript">
startList = function() {
  if (document.all&&document.getElementsByTagName) {
    navRoot = document.getElementsByTagName('ul')[0];
    navRoot.className="menu";
    for (i=0; i<navRoot.childNodes.length; i++) {
      node = navRoot.childNodes[i];
      if (node.nodeName=="LI") {
        node.onmouseover=function() {
          this.className+=" over";
        }
        node.onmouseout=function() {
          this.className=this.className.replace(" over", "");
        }
      }
    }
  }
}
window.onload=startList;
</script>
  <ul class="menu">
    <li class="primera">UL MENU</li>
    <li class="segunda">UL MENU</li>
  </ul>
</body>
</html>  En FF funciona perfecto, quiere decir que la primer fila se pone roja y la segunda gris, pero en IE solo me toma el gris. Como que el Javascript no asinga bien el over teniendo en cuenta la clase que ya tenía. 
Me entiendo ? 
Bueno, desde ya muchas gracias por sus respuestas. 
PD: ivangc, el problema que te comenté antes lo solucioné en vez de poner [0] le puse la posición que ocupaba dicho UL en la página, como iba a estar en un encabezado, simpre será el tercer UL que aparezca en la página, por eso le puse [2]