Então, exatamente tudo isso, nesta mesma ordem (/etc/init.d, permissão de execução e update-rc.d).
Tentei até não usar o update-rc.d, criando os links simbólicos "na mão" com fazia em outros linuxes, e não funciona.
Tem que ter alguma coisa em especial no script para ele rodar (agora, neste contexto do Ubuntu 9.10)?
É um script simples, com função de start/stop/restart que basicamente "pilota" o iptables e rotas - aprendi iptables do jeito difícil e agora não largo.
Obrigado!
Fabio