Eu encontrei uma solução:
Eu instalei um novo kernel.
Seguindo este manual do manual do Ubuntu eu apaguei o antigo versões de kernels
Depois disso, descobri que o linux-image-4.4.0-65-generic estava em um estado inconsistente muito ruim.
Então eu removi usando este comando: sudo dpkg --remove --force-remove-reinstreq <image-to-remove>
.
Agora funciona:)