Edite o arquivo de interfaces para remover
auto eth0
iface eth0 inet dhcp
Salve e reinicie. Use o Network Manager para editar a conexão e configurá-la para se conectar automaticamente.
Este comando irá abrir o arquivo de interfaces no Gedit com permissão para salvar o arquivo:
sudo gedit /etc/network/interfaces
Eu tenho uma conexão com fio e sem fio e tudo o que há no meu arquivo de interfaces são essas duas linhas
auto lo
iface lo inet loopback
Eu descobri por experiência que qualquer outra coisa impedirá uma conexão e remover o que é extra resolverá o problema.