Isso soa exatamente como um problema de DNS. A fim de realmente consertar seu problema, você deve ter declarado qual ambiente de área de trabalho você está usando, pois alguns ambientes de desktop, como o KDE, têm suas próprias funções para problemas como este. Como você não informou qual deles está usando, presumo que esteja usando o Unity (já que ele já está instalado por padrão).
Em primeiro lugar, verifique com qualquer outro programa que você tenha instalado usa a internet, como um jogo, etc. e veja se esse programa / jogo pode realmente acessar a internet. Se puder, mesmo que os navegadores da Internet "não possam", pode até ser tão simples quanto um proxy sendo definido quando você não precisa usar um proxy. Nas configurações dos navegadores, tente desativar proxys e ver se isso resolve o problema.
Se não, então poderia ser um problema de DNS. Sugiro abrir o Terminal e digitar: dpkg-reconfigure resolvconf e veja se isso resolve o seu problema.