Finalmente, encontrei o motivo. Há algum tempo fiz algumas alterações no arquivo /etc/grubd.d/10_linux. Por motivos de segurança, fiz uma cópia deste arquivo (.bak). Este arquivo ainda era executável. Nunca causou problemas até a última atualização do sistema. A única coisa que eu tinha que fazer era um chmod, então esse arquivo (.bak) então ele não era mais executável. Fazendo sudo update-grub todos os arquivos que estão presentes no /etc/grub.d e são executáveis são tomados no arquivo grub.cfg, o que causou o problema.