Essas mensagens de erro correspondem a um problema que o driver r8169 em alguns kernels tem com algum hardware, fazendo com que ele perca repetidamente o link (descrito como "paralisia") apenas para recuperá-lo posteriormente, geralmente resultando em problemas de conexão. O Ubuntu tem um relatório de bug para uma versão mais antiga que não foi resolvida no link .
Uma atualização do kernel pode fazê-lo desaparecer, e resolveu com sucesso o problema para alguns, e há alguma discussão sobre uma correção que supostamente funcionou em link , mas no meu sistema (Debian Unstable) com um 2.6 bastante recente. O kernel 3x, a única maneira confiável de resolver o problema, foi instalar o driver de terceiros da Realtek para o hardware, carregando o nome 8168, que não tem esse problema. Eu tentaria essas coisas nessa ordem.
Não sei como esse problema pode estar relacionado a reinicializações inesperadas. As mensagens podem não estar relacionadas ao seu problema original de reinicializações, pode estar dando uma virada particularmente séria em sua máquina ou você pode ter sintomas semelhantes, mas um problema totalmente diferente para essa.