Eu nunca tive o Ubuntu se comportando assim, então isso é apenas um palpite: pode ter algo a ver com 'network-manager'.
Quanto à remoção do dhcp-client:
Você está tentando remover um pacote virtual. Pacotes virtuais realmente não existem, apenas são fornecidos por alguns pacotes para declarar que eles fornecem um serviço / função similar (veja também Manual de Normas Debian . IIRC o pacote dhcp-client padrão instalado pelo ubuntu é 'isc-dhcp-client', mas não importa qual deles está instalado em seu sistema você provavelmente terá dificuldade em removê-lo corretamente já que alguns outros pacotes dependem de sua instalação .