A questão aqui acabou sendo algumas coisas. Como abarnert apontou nos comentários da pergunta, houve uma mistura do python do sistema e do python virtualenv. Para resolver isso, tive que alterar as propriedades do projeto PyDev para apontar apenas para a instância virtualenv python, então nas preferências do interpretador PyDev tive que reconstruir o PYTHONPATH.
Feito isso, no virtualenv tive que executar o seguinte código:
pip uninstall mysql-python
pip install mysql-python==1.2.5
Isso resolveu todos os problemas.
