Finalmente descobri qual era o meu problema.
python-mysql.connector não era um pacote py3 e o apt-get nem o aptitude estavam propondo tal versão.
Eu consegui instalá-lo com pip3 que não era tão simples no Ubuntu 12.04 porque ele só vem com o Ubuntu a partir de 12.10 e o pacote não tem o mesmo nome em pip ...
[email protected]:$sudo apt-get install python3-setuptools [email protected]:$sudo easy_install3 pip [email protected]:$ pip --version pip 1.4.1 from /usr/local/lib/python3.2/dist-packages/pip-1.4.1-py3.2.egg (python 3.2) [email protected]:$sudo pip install mysql-connector-python
