Проблемът тук се оказа в няколко неща. Както abarart посочи в коментарите на въпроса, имаше смесване на системния python и virtualenv python. За да разреша това, трябваше да променя свойствата на проекта на проекта PyDev, за да сочат само към екземпляра на python virtualenv, след което в предпочитанията на интерпретатора на PyDev трябваше да изградя отново PYTHONPATH.
След като това беше направено, във virtualenv трябваше да изпълня следния код:
pip uninstall mysql-python
pip install mysql-python==1.2.5
Това разреши всички проблеми.
