OK, I have been biking mercurial for a while and wanted to upgrade to the latest version
In the process of that, I got the error python headers are required to build mercurial
Here is the fix.
sudo apt-get install build-essential gcc python-dev
which it was missing.
For re-installation follow the steps listed on https://help.ubuntu.com/community/Mercurial