Los usuarios de LMDE posiblemente se encuentren con una situación muy curiosa en la configuración de la tarjeta de red.
Normalmente la interface de red por defecto en Debian, Ubuntu y demás, es eth0, pero al instalar LMDE este número se corre y pasa a ser eth1. En mi caso, que tengo 2 tarjetas de red, eth0 y eth1, pasan a ser eth1 y eth2 respectivamente.
Me puse a buscar y la solución que encontré para esto es eliminar el paquete dnet-common si está instalado.
$ sudo aptitude purge dnet-common
Reiniciamos y todo deberÃa funcionar de nuevo.