Eu encontrei a solução.
Não sei qual foi exatamente o problema, mas esse problema parece ter desaparecido em uma nova instalação do 16.04. Talvez eles atualizaram as dependências corretamente? Não tenho certeza. Mas posso confirmar pessoalmente que isso não é mais um problema em 16.04