Você deve procurá-lo nos diretórios da plataforma. Para mim, tudo o que foi preciso foi adicionar a seguinte opção de configuração:
--with-libiberty=/usr/lib/i386-linux-gnu/
Como descobri que era simples encontrar na linha de comando:
find /usr/ -iname '*iberty*'
Que retornou alguns arquivos de cabeçalho e /usr/lib/i386-linux-gnu/libiberty.a
.