Você usou apenas update-grub2 após excluir a partição?
Se for esse o caso, depois de excluir outra partição, tente sudo grub-install /dev/sdx onde sdx é o HDD onde a instalação atual do Ubuntu reside.e.g. sda se primeiro disco rígido. Em seguida, faça um sudo update-grub2 . Desta forma, você estará certo de que está atualizando o grub da instalação atual e não o outro.