A coisa "não há espaço suficiente na inicialização" é uma questão independente, que parece ser um problema constante para as pessoas que têm a criptografia de disco ativada. Parece ter sido relatado como um relatório de bug há um ano, mas ainda não está corrigido por algum motivo. Você pode consertar isso com
dpkg -l 'linux-*' | sed '/^ii/!d;/'"$(uname -r | sed "s/\(.*\)-\([^0-9]\+\)//")"'/d;s/^[^ ]* [^ ]* \([^ ]*\).*//;/[0-9]/!d' | xargs sudo apt-get -y purge
no console - isso procura quais pacotes de kernel você instalou e, em seguida, remove todos eles do que você está executando atualmente.