Provavelmente você tem um problema com o cache do resolvedor de DNS. O resolvedor de DNS traduz nomes de domínio para endereços IP e vice-versa. Provavelmente, a entrada no seu cache DNS não é mais válida.
Você pode tentar atualizar seu cache reiniciando o serviço DNS:
sudo service nscd restart
Se isso não funcionar, tente isso
sudo service network-manager restart