Eu não posso comentar (devido à minha reputação), então parece que eu tenho que escrever uma resposta ...
Eu tive esse problema há alguns dias, mas foi porque eu restaurei uma imagem (clonezilla) em uma nova partição, e, cada vez que você cria a partição (eu não sei, talvez também quando você formata), ele fica um novo UUID, diferente daquele armazenado no conteúdo da imagem.
Em qualquer caso: procure aquele UUID (aquele que você coloca com xxxx) em /boot/grub/grub.cfg e /boot/grub/i386-pc/load.cfg e corrija-o corretamente ... MAS, caso você recriar a partição (que era o meu caso), não mude o UUID nesses arquivos, é melhor mudar o novo UUID da partição para o anterior que tinha com:
tune2fs / dev / {device} -U {uuid}