Eu tive um problema semelhante no Ubuntu 16.04.4 LTS e foi causado por espaço insuficiente em disco / boot ( Sem espaço deixado no dispositivo ). Consegui resolver o problema com o seguinte comando para remover e limpar os kernels antigos instalados, mantendo o kernel atual:
sudo apt-get remove --purge $(dpkg -l 'linux-image-*' | sed '/^ii/!d;/'"$(uname -r| sed "s/\(.*\)-\([^0-9]\+\)//")"'/d;s/^[^ ]* [^ ]* \([^ ]*\).*//;/[0-9]/!d')
Esta pode não ser uma solução segura, pois manterá o kernel atual apenas ao remover todos os outros kernels. Espero que isso ajude!