I had a really hard time finding this, so I’m posting it here:

First one must install all the proper packages on Natty (these are the packages needed for zlib and sqlite in general, not just specifically for Python):

sudo apt-get install zlibc zlib1g zlib1g-dev
sudo apt-get install sqlite3-dev

Then one must add an LDFlag to the new lib directories (apparently Natty has a new directory for X86_64 lib files):

after the ./configure open your Makefile and find the line with LDFLAGS=edit to LDFLAGS=-L/usr/lib//x86_64-linux-gnu and make

Credit for the above snippet goes to Awin Abi and source is below:

http://groups.google.com/group/google-appengine/browse_thread/thread/a8bd0a71270a3ce6

Basically, setting up Python2.5 ( and presumably any version of Python) properly involves downloading the proper package libraries , then building Python2.5 with those packages. In order to do this, the LDFlags variable must have the new library location (the /usr/lib/x86-64-linux-gnu) for Natty and 64-bit processors added.

I have not tried this on a 32-bit machine. This may not be required then, or you may need to point the flag to load the proper directory.