Então vamos ser radicais. Entre no Gerenciador de pacotes Synaptic, vá em Configurações/Repositórios/Programas de terceiros e desmarque tudo o que tem lá. Feche, clique no botão recarregar e tente novamente instalar o build-essential. Na pior das hipóteses você vai ter que substituir seu sources.list pelo original. Não vejo outro motivo pra isso senão conflito entre repositórios.