Tem certeza de que a instalação foi concluída com sucesso? Você recebe esse erro quando os cabeçalhos do kernel não estão disponíveis. Se for possível fazer LiveCD na máquina, acredito que você possa fazer chroot no sistema de arquivos do RHEL e, em seguida, atualizar. Isso pode consertá-lo.