Skończyło się na tym, że problem dotyczył kilku rzeczy. Jak zauważył abarnert w komentarzach do pytania, nastąpiło pomieszanie pythona systemowego i pytona virtualenv. Aby rozwiązać ten problem, musiałem zmienić właściwości projektu projektu PyDev, aby wskazywał tylko na instancję virtualenv python, a następnie w preferencjach interpretera PyDev musiałem przebudować PYTHONPATH.
Po wykonaniu tej czynności w virtualenv musiałem uruchomić następujący kod:
pip uninstall mysql-python
pip install mysql-python==1.2.5
To rozwiązało wszystkie problemy.
