Parece que executar sudo apt-get upgrade && apt-get update
resolve o problema. Percebi que enquanto o problema estava acontecendo no meu sistema, nenhum dos repos da Canonical ou de qualquer outro tipo de repositório estava habilitado. Deve haver algo errado com o sistema de gerenciamento de pacotes ...