Where is the python library installed?
This message is not asking for the python libraries themselves, it's asking for the headers to link against them. You can install then with:
sudo apt-get install python-dev
You are probably lacking some other dependencies.
You should be able to find it in the following locations
/usr/lib//usr/local/lib/
I found myself in the same situation with VAMOS Automotive Simulator. The Python version was hardcoded in the configure file, so I had to install that version instead, in my case:
apt-get install python3.4-dev