Eu removi os links simbólicos postados na minha pergunta.
Depois, com a sugestão do @ shuttle87, em askubuntu
Eu fiz o seguinte:
sudo apt-get install --reinstall binutils
sudo apt-get install --reinstall build-essential
sudo apt-get install --reinstall libc6-dev
sudo apt-get install --reinstall gcc-4.7-multilib
sudo apt-get install --reinstall g++-4.7-multilib
Então isso funcionou: gcc -m32 foo.c
para compilar para 80386.
Mas para compilar para x86-64 gcc foo.c não funcionou.
Então eu tentei:
gcc foo.c -L /usr/lib/x86_64-linux-gnu
Mas isso também não funcionou. Finalmente tive que:
export LIBRARY_PATH=/usr/lib/x86_64-linux-gnu
Antes que gcc foo.c funcionasse.
Eu usei "readelf -h" para verificar se os executáveis eram 80386 e X86-64.
Não entenda porque a bandeira 'L' não funcionou ...
Mas pelo menos eu removi esses links simbólicos e posso compilar com facilidade usando a "exportação".