Konečně jsem přišel na to, co mám za problém.
python-mysql.connector nebyl balíček py3 a apt-get ani aptitude takovou verzi nenabízely.
Podařilo se mi jej nainstalovat pomocí pip3, což na ubuntu 12.04 nebylo tak jednoduché, protože je dodáváno pouze s ubuntu od 12.10 a balíček pod pip nemá stejný název...
example@sqldat.com:$sudo apt-get install python3-setuptools example@sqldat.com:$sudo easy_install3 pip example@sqldat.com:$ pip --version pip 1.4.1 from /usr/local/lib/python3.2/dist-packages/pip-1.4.1-py3.2.egg (python 3.2) example@sqldat.com:$sudo pip install mysql-connector-python