Eu não posso dizer o que faz com que o erro volte como espaço em disco, mas encontrei exatamente esse problema hoje à noite e resolvi-o removendo manualmente alguns dos cabeçalhos antigos e continuando normalmente.
sudo rm -rf /usr/src/linux-headers-4.4.0-5*
sudo rm -rf /usr/src/linux-headers-4.4.0-6*
Depois disso, consegui usar o apt para todo o resto, como normal.