Вы используете Unity или Gnome 3? TortoiseHg является расширением Nautilus, поэтому будет работать только с Gnome.
Также, похоже, сообщается о проблемах совместимости TortoiseHg с Gnome3:
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=644697
https://bitbucket.org/tortoisehg/thg/issue/869/tortoisehg-nautilus-doesnt-work-at-all
Не знаю, были ли эти проблемы исправлены в последней версии TortoiseHg. Возможно, стоит попробовать TortoiseHg PPA получить последнюю версию, поскольку версия, которая есть в стандартных репозиториях Ubuntu, как правило, немного отстает.
Обновить:
Там какая - то информация здесь относительно его снова работает в 12.10.