Eu fiz o que você mencionou, e eu não tive problemas para inicializar o Kali no GRUB. Eu removi a mídia de instalação e ela simplesmente funcionou.
De qualquer forma, você pode editar o comando boot no grub na primeira vez para modificar a partição de inicialização e acessar a interface gráfica. Então, basta configurar o GRUB para usar o UUID do disco em vez dos nomes sdX.
Você pode fazer isso seguindo um processo semelhante a este: link