Eu quase fiz isso inicialmente. Apenas não vá em frente e faça update-grub
novamente. Então, foi assim que o problema foi resolvido.
Instalei pela primeira vez os-prober
fazendo o seguinte -
$ sudo apt install os-prober
Então, como mencionado anteriormente na minha pergunta, fez -
$ sudo os-prober
/dev/sda2:Ubuntu 16.04.3 LTS (16.04):Ubuntu:linux
E foi capaz de detectar meu outro SO.
Então eu fui em frente e fiz -
$ sudo update-grub
Generating grub configuration file ...
Found linux image: /boot/vmlinuz-4.4.0-92-generic
Found initrd image: /boot/initrd.img-4.4.0-92-generic
Found linux image: /boot/vmlinuz-4.4.0-79-generic
Found initrd image: /boot/initrd.img-4.4.0-79-generic
Found linux image: /boot/vmlinuz-4.0.0-kali1-amd64
Found initrd image: /boot/initrd.img-4.0.0-kali1-amd64
Found Ubuntu 16.04.3 LTS (16.04) on /dev/sda2
Adding boot menu entry for EFI firmware configuration
done
E foi isso. Agora, ambos os sistemas operacionais estão visíveis no meu menu grub.