The error I was getting after activating the virtualenv and running pip install python-ldap was related to gcc missing, which was misleading since that wasn't actually the issue:
error: Setup script exited with error: command 'gcc' failed with exit status 1
To add to the weirdness, when I installed python-ldap outside the context of a virtualenv, everything worked fine.
I'll save you the blow-by-blow and just tell you that on my machine at least, other than the required OpenLDAP installation and some other libraries, I also had to install libsasl2-dev:
sudo apt-get install libsasl2-dev
Once I had that installed, I could activate my virtualenv, run pip install python-ldap and install without errors.
If you still run into issues make sure (in addition to OpenLDAP) to have these packages installed:
Hope that saves someone else some time!