O problema é que havia, entre outros, dois arquivos no meu /boot/grub/ : stage2 e stage2.old . O último hat uma data de arquivo de janeiro de 2012, enquanto o primeiro foi alterado nos últimos dias. Eu substituí stage2 por stage2.old e funcionou novamente.
No entanto, gostaria de saber se alguém mais teve esse problema e talvez saiba de onde veio essa alteração ...