Make sure that the header files are installed:
dpkg-query -l | grep python.*-dev
If not:
sudo aptitude install python2.5-dev
or
sudo aptitude install python-dev