У меня была та же проблема.
Установка Mercurial с ubuntuupdates.org
, а затем установка tortoiseHg с использованием sudo apt-get install tortoisehg решила мою проблему.