O Bash mantém um cache de locais de executáveis em $PATH . Você teve hg em /usr/bin em algum momento e executou esse shell. Agora você removeu /usr/bin/hg . Você precisa dizer ao seu shell em execução para esquecer este local:
hash hg
Um novo shell não teria esse problema, já que o cache não é compartilhado entre as instâncias do shell.