Tanto a duplicidade quanto o python-gi estão de fato nos repositórios 16.04.
Este tipo de erro geralmente ocorre em uma nova instalação se você ainda não executou sudo apt update
pela primeira vez, já que a base de dados do apt ainda está vazia.