For the case of CentOS, I had this very same problem, that I solved installing these packages:
sudo yum install postgresql-libssudo yum install postgresql-develsudo yum install python-devel
only then, I was able to perform successfully:
sudo easy_install psycopg2