Além do que o OP descreve, minha atualização de lançamento foi interrompida por esse problema. O comentário de Josh.F fez o truque para mim:
sudo add-apt-repository ppa:ubuntu-toolchain-r/test
sudo apt-get update
sudo apt-get -f install
Isso corrigiu o gcc-5 para mim e ainda precisei sudo apt-get upgrade