Está um pouco atrasado agora, mas acabei de ter um problema semelhante ao instalar o Arch (pela primeira vez). Acontece que, por qualquer motivo, a instalação do pacote cria o kernel e as imagens initramfs com nomes diferentes daqueles utilizados pelo Grub. Tudo o resto, incluindo UUIDs, estava bem.
Os nomes de arquivo padrão com os quais acabei foram /vmlinuz-linux
(no lugar de /vmlinuz26
) e /initramfs-linux.img
( /kernel26.img
) - inicializando a partir do live CD e modificando /boot/grub/menu.lst
para substituir o kernel e initramfs eu bota.
Sobre como isso aconteceu em primeiro lugar, eu acho que o script de instalação do Arch simplesmente não passa os nomes dos arquivos de saída da instalação do kernel para a criação do menu do Grub. É frustrante, porém, e não uma ótima introdução ao que muitas vezes é considerado uma das melhores distribuições.