Pequeña ayuda con getElementsByTagName

[ivangc]

Es normal, solo estás cogiendo el elemento 0 de la colección de tags encontrados:
navRoot = document.getElementsByTagName('ul')[0];

Debes hacer un bucle para recorrer toda la coleccion y no quedarte solo en el primero:
var elements = document.getElementsByTagName('ul');
var j;
for (j=0; j < elements.length; j++)
{
navRoot = document.getElementsByTagName('ul')[j];
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", "");
}
}
}
}
Sería algo así, no lo he probado pero para que te hagas una idea...