It sounds like a problem with the python-qgis-common package just try removing it with the --purge option and then reinstalling you might have to wrestle with dependencies, though it doesn't sound like anything that depends on it is installing.
If you ultimately cannot get it to work you might need to purge everything from your system and reinstall. Then run sudo apt-get remove --purge qgis This should remove qgis, all it dependencies that are not needed elsewhere, and all configuration files except the ones in your home folder (I think, they should be at ~/.qgis and ~/.config/QuantumGIS). You can also do this via Synaptic via the Removal All on your check-boxes.
This should reset everything as it was before package install.
If you installed from source, and you still have your source files you can run make uninstall this should do about the same as above but won't touch your dependencies or any configuration files(?).
Next time if installing from source use the checkinstall packagecheckinstall package it will neatly make a *.deb file from your source and can use aptitude to manage your packages. http://stackoverflow.com/a/308961/784411
**Be warned I am not using 1.9