Depois de pesquisar por um tempo em System Settings > Software & Updates Lembrei-me de uma vez que desabilitei as atualizações de instalação das seguintes fontes porque fiquei um pouco irritado com os pop-ups de interrupção frequentes para atualizar. Eu prefiro gerenciar meus upgrades manualmente a partir de apt no terminal e eu não quero que ele me atualize automaticamente de 16.04 para 16.10 ou algum outro release. O que eu não percebi é que essas caixas de seleção retiraram as fontes do pacote deb de /etc/apt/sources.list , para que ele nunca buscasse as atualizações do pacote e sempre informasse que meu sistema estava atualizado. Depois de verificar essas caixas e, em seguida, executar apt update e upgrade , consegui instalar com êxito o ldap-utils