No Ubuntu 14.04 e abaixo, há um arquivo localizado em /etc/init/rc-sysconfig.conf ou /etc/init/failsafe.conf que pausa o processo de inicialização por até dois minutos se as NICs na máquina não estiverem ativas.
O Ubuntu 16.04 parece acabar com esses dois arquivos, mas ainda há um atraso se demorar um pouco para trazer as interfaces de rede para cima.
Onde esse atraso está configurado em 16.04 e acima?