Una volta installato il pacchetto in questione devi specificare sulla linea di comando di gcc
codice:
-I/usr/include/python
in modo che vada a cercare gli include anche lì. Comunque se è un progetto già fatto si spera che abbia un qualche build system che avvii il compilatore con le opzioni corrette... non c'è un makefile/uno script configure/un CMakelist.txt o roba simile?