Graças ao comentário do Katu, agora sei que os UUIDs são armazenados em superblocos para sistemas de arquivos Linux (ext2 / 3/4). E eu instalei o Linux no ext fs, btw. Então, eu entendo que o UUID não é algo que cada entidade do sistema faz para seu próprio uso, mas o mesmo para a mesma partição.
Por que o instalador colocou esse UUID em grub.cfg
permaneceu um mistério para mim, no entanto, depois que eu editei o arquivo e substitui o UUID lá pelo UUID dado pelo blkid para o meu root fs, o Linux começou normalmente.