OK. Veja só, essa interface gigabit, por algum motivo, não está sendo reconhecida da primeira vez que você inicia a máquina. Isso, por si só, não é um bom sinal, o suporte a interfaces de rede cabeada é muito estável e muito extenso, é muito raro hoje em dia encontrar uma placa de rede que não seja suportada.
Agora, o mais estranho é você rebootar e o driver ser reconhecido...
Bem, o que podemos fazer é forçar a carga do driver no boot; mas ainda vamos precisar alguns testes. Da próxima vez que o acesso falhar, execute o comando abaixo e diga se a internet funciona.
sudo modprobe -v e1000e