Para minha lembrança, o Ubuntu usa o GRUB2, não o GRUB (agora, o GRUB Legacy) - isso pode ajudar na busca de respostas. A maneira como eu faria o meu sistema inicializar novamente depois de embaralhar as partições (presumivelmente, usando algo como o PartitionMagic) é inicializar de um LiveCD, instalar minhas partições Linux e depois fazer o chroot no sistema Linux. A partir daí, faça uma cópia de backup de sua configuração do GRUB2 e execute
grub-mkconfig -o /boot/grub/grub.cfg
grub-install
Isso deve colocá-lo de volta em funcionamento.