você já tentou:
sudo apt-get install -f
sudo apt-get update
se não funcionar, tente:
sudo apt-get install ppa-purge
sudo ppa-purge ppa:ubuntu-toolchain-r/test
Entre em fontes de software e verifique se você tem o universo e os repositórios multiversos habilitados, então
sudo apt-get update
Em seguida, tente instalar novamente
sudo apt-get install gcc-4.8 g++-4.8
e por favor, liste seu arquivo sources.list