Promisse

Seu for deve ser dentro do callback de sucesso. Lembre-se que promises são assíncronas :) Se você quer garantir que um código seja executado assim que ela for concluída, tem que colocar dentro de success. Sendo assim, seu código fica:

MenuService.consultar(IdPai)
        .success(function (results) {
            submenus = results;
            for (i=0; i < submenus.length; i++) {
              .... codigo aqui
            }
        })
        .error(function (error) {
            console.log('erro: ' + error);
        });

Flavio interessante e que fiz esse codigo acima antes de enviar esse questionamento, mas mesmo assim, usando o debug do chrome para analisar, identifico que o for não roda, pois o submenu.lenght é undefined, mas se olho os valores do result na linha de cima, eles tem 3 objetos e o length dele é 3. Tem ideia do que possa ser?

Results tem valor? É um array? O problema parece estar no seu backend que não devolve o dado esperado. Exiba no console o valor de results e me diz o que aparece. Cole o que é exibido no console.

Cole também o código com suas alterações. Mas o for tem que ficar em success de qualquer jeito