your system doesn't have python-dev package. If you are compiling mercurial from source you need that. Install that first and try again.
(on debian based systems) $> sudo apt-get install python-dev I prefer this, because, one in ubuntu repo is older than latest version available, And since some of my repo's are created with newer version, older versions of mercurial can't operate on them.