o pacote "apt-xapian-index" está no repositório do universo desde o Ubuntu 16.04 Xenial (veja link ). Antes do Ubuntu 16.04 Xenial o pacote "apt-xapian-index" estava no repositório principal, então ele estava sempre disponível, mesmo se o usuário tivesse o repositório "universe" desativado. Não é mais o caso.
Para confirmar o que está acima, basta executar o seguinte:
apt-cache policy apt-xapian-index
Se o resultado não estiver disponível, é porque o apt-get não pode encontrá-lo nos repositórios presentes no arquivo /etc/apt/sources.list.
Meu palpite é que você removeu / desabilitou o repositório do universo do seu arquivo APT /etc/apt/sources.list. Certifique-se de adicionar "universo" no final das linhas começando com "deb" nesse arquivo. Por exemplo, altere a seguinte linha para que o repositório do universo seja ativado, no arquivo /etc/apt/sources.list:
deb http://archive.ubuntu.com/ubuntu/ xenial main
Para algo como (adicione a última palavra na linha):
deb http://archive.ubuntu.com/ubuntu/ xenial main universe
Em seguida, atualize os repositórios do apt-get:
sudo apt-get update
O Apt-get atualizará suas fontes de pacotes disponíveis, agora com o repositório universe ativado. Em seguida, tente resolver o problema:
sudo apt-get install -f