One suggestion I can tell at the moment is to define an Environmenl variable
PYTHONPATH set to your home installation's lib directory. From what I am seeing
in my attempt to reproduce this error, even though your hg main binary is
running from right location, the modules it imports internally are not the ones
which you have installed now, meaning you are still using old version of
mercurial :)

Since you said you are on Ubuntu, try adding this line to your $HOME/.bashrc (or
configuration file of
which ever shell you are using)
export PYTHONPATH=$HOME/lib/python
(The of install path of mercurial's modules is $HOME/lib/python since you said
you have run make install-home)
This should work fine. Please inform us what happened.