Problemet här slutade med att vara några saker. Som abarnert påpekade i kommentarerna till frågan, var det en blandning av system-python och virtualenv-python. För att lösa detta var jag tvungen att ändra projektegenskaperna för PyDev-projektet till att bara peka på virtualenv python-instansen, sedan i PyDev-tolkinställningarna var jag tvungen att bygga om PYTHONPATH.
Efter att detta var gjort var jag tvungen att köra följande kod i virtualenv:
pip uninstall mysql-python
pip install mysql-python==1.2.5
Detta löste alla problem.