After trying a few things, this worked for me:
go to your virtualenv directory (but don't run workon):
cd ~/.virtualenv/name_of_broken_venv
Now delete these files:
rm -rf .Python bin/python* lib/python2.7/* include/python2.7
Then to rebuild your venv, run:
virtualenv .
workon name_of_broken_venv
pip freeze