Como eu disse no meu comentário, o problema não é um bug no GCC ou no Ubuntu, mas sim um recurso incompatível: multiarch . O objetivo do multiarch é permitir que binários para várias arquiteturas sejam instalados no mesmo sistema de arquivos ao mesmo tempo sem colisões. Isso substituirá o antigo sistema de bibliotecas de 32 bits vs. 64 bits que existia, mas é realmente mais importante onde queremos ter o Intel e o ARM instalados de uma só vez, por exemplo. Presumivelmente, isso não é muito interessante para computadores de mesa, mas o Ubuntu existe em muitos dispositivos incorporados (ou serve) que podem fazer esse tipo de coisa.
Fazer alterações como essa naturalmente resulta na movimentação de arquivos, portanto, podemos esperar algumas interrupções durante o período de transição. Atualmente, o GCC não oferece suporte aos novos locais, mas acabará fazendo isso.
A partir de uma instalação padrão na área de trabalho, essas etapas de configuração permitiram que a compilação funcionasse para mim:
amd64 (testei este aqui):
sudo -i
# apt-get install libppl0.11-dev libmpfr-dev libgmp-dev libc6-dev-i386
# cd /usr/include
# ln -s x86_64-linux-gnu/* .
# cd /usr/lib
# ln -s x86_64-linux-gnu/crt* .
Eu vejo que você está usando o Ubuntu de 32 bits. Eu não testei isso, mas fiz as mudanças óbvias.
ix86:
sudo -i
# apt-get install libppl0.11-dev libmpfr-dev libgmp-dev libc6-dev
# cd /usr/include
# ln -s i386-linux-gnu/* .
# cd /usr/lib
# ln -s i386-linux-gnu/crt* .
AVISO: a inserção dos links não é, em geral, inofensiva, para a maioria das pessoas, mas pode causar problemas futuros. (Principalmente apenas se você deseja criar projetos de 64 e 32 bits na mesma máquina.)