Você está usando o Unity ou o Gnome 3? O TortoiseHg é uma extensão do Nautilus, portanto só funcionará com o Gnome.
Também parece haver problemas sendo relatados com a compatibilidade do TortoiseHg com o Gnome3:
Não sei se estes problemas foram corrigidos na última versão do TortoiseHg. Pode valer a pena tentar com o PPA do TortoiseHg para obter a versão mais recente, já que a versão que está nos repositórios padrão do Ubuntu tendem a atrasar um pouco.
Atualização:
Há algumas informações aqui a respeito de seu funcionamento novamente 12.10.