Finalmente ho capito qual era il mio problema.
python-mysql.connector non era un pacchetto py3 e apt-get né aptitude proponevano tale versione.
Sono riuscito a installarlo con pip3 che non era così semplice su Ubuntu 12.04 perché è in bundle con Ubuntu solo a partire da 12.10 e il pacchetto non ha lo stesso nome sotto pip...
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