I had this issue on Ubuntu server 12.04.
I had to install libfreetype6-dev and libpng-dev from the repositories. I was using a virtualenv and installing matplotlib using pip when I ran into this issue.
Hints that I needed to do this came from the warning messages that popup early in the matplotlib installation so keep an eye out for those messages which indicate a dependency is found, but not the headers.