Ok, acho que do-release-upgrade
levou a sério a necessidade de espaço na unidade raiz.
Ele também verifica o espaço livre em um monte de outras pastas, mas na verdade precisava dos 600 MB extras para estar em /
. Eu acho que foi a quantidade de espaço que as novas versões de todos os meus pacotes ocupariam.
Consegui limpar espaço suficiente removendo todos os meus kernels linux antigos (eles não são removidos automaticamente!) e está baixando a atualização agora.