Hola 
leo_25: 
Viéndolo así ya nos podemos hacer a la idea. La estructura cambia, no sólo hay rubros[1] sino que hay rubros[1], [2], [3].... 
Bueno, este script está preparado, creo, para todo lo que pides:  
 Código PHP:
    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="es" lang="es">
<head>
<meta http-equiv="Content-type" content="text/html;charset=iso-8859-1" />
<meta name="Author" content="derkeNuke" />
<title>Página nueva</title>
<style type="text/css">
</style>
</head>
<body>
<form onsubmit="return valida(this)" action="">
    <input type='checkbox' name='rubros[1]' value='x' />Alimentos
    <ul id="uno">
        <li><input type='checkbox' name='subrubros[1][2]' value='a' />Frutas</li>
        <li><input type='checkbox' name='subrubros[1][3]' value='b' />Verduras</li>
    </ul>
    <input type='checkbox' name='rubros[2]' value='x' />Prendas de vestir
    <ul id="dos">
        <li><input type='checkbox' name='subrubros[2][2]' value='a' />Vestidos</li>
        <li><input type='checkbox' name='subrubros[2][3]' value='b' />Camisas</li>
    </ul>
<input type='checkbox' name='rubros[3]' value='x' />Bebidas
    <ul id="">
        <li><input type='checkbox' name='subrubros[3][2]' value='a' />Gaseosas</li>
        <li><input type='checkbox' name='subrubros[3][3]' value='b' />Agua Mineral</li>
    </ul>
    <button type="submit">Envia</button>
</form>
<script type="text/javascript">
<!--
function valida(fr) {
    var hayRubroSeleccionado = false;
    // Buscamos e iteramos con todos los elementos que se llamen rubros[x]
    for(var x=1, rubroX; (rubroX = fr["rubros["+x+"]"]); x++) {
        // Siempre que esté seleccionado
        if( rubroX.checked ) {
            hayRubroSeleccionado = true;
            //Validemos si hay subrubros seleccionados
            // Vamos mirando su hermano y el hermano del hermano hasta encontrar un UL
            var hermanoUL = rubroX.nextSibling;
            if( hermanoUL.nodeType!=1 || hermanoUL.tagName.toUpperCase()!="UL" )
                hermanoUL = hermanoUL.nextSibling;
            //Ahora hermanoUL será la lista que hay al lado (que damos por entendido que contiene los subrubros)
            var LIsubrubros = hermanoUL.getElementsByTagName("LI");
            var srSeleccionados = 0;            // número de sburubros seleccionados
            for(var j=0; j<LIsubrubros.length; j++) {        //recorremos los elementos LI
                if( LIsubrubros[j].firstChild.checked )            //firstChild será el checkbox si no dejamos espacios en el xHTML
                    srSeleccionados++;
            }
            if( srSeleccionados == 0 ) {
                alert("Debe seleccionar algún subrubro para '"+rubroX.nextSibling.nodeValue+"'");
                return false;
            }
        } //if rubro.checked
    }
    // Comprobamos que haya al menos un rubro seleccionado. Si hay devolvemos true, si no hay devolvemos false
    if( hayRubroSeleccionado ) {
        alert("Todo correcto!");
    }
    else {
        alert("Debe seleccionar al menos un rubro");
        return false;
    }
}
// -->
</script>
</body>
</html> 
   
  
Testéalo. Supongo que nos quedarán pocas modificaciones para la versión final.  
Un saludo 
