Descobriu que duas coisas estavam erradas:
- Meu / boot estava 95% cheio e não podia continuar com a atualização.
- Houve um PPA estragando tudo e o removi do /etc/apt/sources.d/
Depois disso, eu limpei minhas imagens linux e executei o apt -get autoremove
Agora parece estar funcionando corretamente novamente.