A resposta é simples: eu tinha o Ubuntu 17.04 instalado, que aparentemente era a forma de atualização mais segura do Ubuntu.
O Ubuntu não parece atualizar de 16.04 diretamente para a versão mais recente.
Funciona tudo bem agora após outro upgrade para de 17.04 a 17.10.
Se, no entanto, você estiver preso a uma situação em que sua atualização não foi planejada, sugiro que veja o arquivo de manifesto do Ubuntu para a sua versão do Ubuntu. Ele contém todos os pacotes que devem ser instalados com uma nova instalação e pode ajudá-lo a descobrir quais deles estão faltando ou quais você pode acionar para reconfigurar. Você pode encontrar uma boa resposta para isso aqui: Como faço para listar o padrão pacotes instalados?