Parecia que todos os arquivos .o necessários estavam instalados, mas a versão ppa do gcc 4.6 que eu estava estava procurando no lugar errado para eles. Reinstalar todos os pacotes do repositório oneric oficial resolveu o problema.
Verifique se você tem acesso aos repositórios corretos e, em seguida:
sudo apt-get update
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.6
sudo apt-get install --reinstall libboost1.46-all-dev