Ok, consegui resolver o problema: instalei o aptitude
sudo apt-get install aptitude
e depois executou o aptitude para instalar o build-essential
sudo aptitude install build-essential
sugeriu o downgrade de alguns pacotes (não aceite a primeira solução que ele propõe, acho que a segunda ou terceira solução foi a que funcionou). No caso de alguém se deparar com o mesmo problema - use o aptitude - como alguém escreveu em outro fórum é como apt-get apenas mais inteligente ...