Problemet her endte med at være et par ting. Som abarnert påpegede i kommentarerne til spørgsmålet, var der en blanding af system python og virtualenv python. For at løse dette var jeg nødt til at ændre projektegenskaberne for PyDev-projektet til kun at pege på virtualenv python-forekomsten, og derefter i PyDev-fortolkerens præferencer var jeg nødt til at genopbygge PYTHONPATH.
Efter at dette var gjort, var jeg nødt til at køre følgende kode i virtualenv:
pip uninstall mysql-python
pip install mysql-python==1.2.5
Dette løste alle problemerne.