Eu só notei que há uma série de python-pyside packages nos repositórios. Atualmente versão 1.1.2 (o mesmo que sua última versão do PPA para Precise).
$ apt-cache search ^python3?-pyside
python-pyside - Python bindings for Qt4 (big metapackage)
python-pyside.phonon - Qt 4 Phonon module - Python bindings
python-pyside.qtcore - Qt 4 core module - Python bindings
python-pyside.qtdeclarative - Qt 4 Declarative module - Python bindings
python-pyside.qtgui - Qt 4 GUI module - Python bindings
python-pyside.qthelp - Qt 4 help module - Python bindings
python-pyside.qtnetwork - Qt 4 network module - Python bindings
python-pyside.qtopengl - Qt 4 OpenGL module - Python bindings
python-pyside.qtscript - Qt 4 script module - Python bindings
python-pyside.qtsql - Qt 4 SQL module - Python bindings
python-pyside.qtsvg - Qt 4 SVG module - Python bindings
python-pyside.qttest - Qt 4 test module - Python bindings
python-pyside.qtuitools - Qt 4 UI tools module - Python bindings
python-pyside.qtwebkit - Qt 4 WebKit module - Python bindings
python-pyside.qtxml - Qt 4 XML module - Python bindings
python3-pyside - Python3 bindings for Qt4 (big metapackage)
python3-pyside.phonon - Qt 4 Phonon module - Python3 bindings
python3-pyside.qtcore - Qt 4 core module - Python3 bindings
python3-pyside.qtdeclarative - Qt 4 Declarative module - Python3 bindings
python3-pyside.qtgui - Qt 4 GUI module - Python3 bindings
python3-pyside.qthelp - Qt 4 help module - Python3 bindings
python3-pyside.qtnetwork - Qt 4 network module - Python3 bindings
python3-pyside.qtopengl - Qt 4 OpenGL module - Python3 bindings
python3-pyside.qtscript - Qt 4 script module - Python3 bindings
python3-pyside.qtsql - Qt 4 SQL module - Python3 bindings
python3-pyside.qtsvg - Qt 4 SVG module - Python3 bindings
python3-pyside.qttest - Qt 4 test module - Python3 bindings
python3-pyside.qtuitools - Qt 4 UI tools module - Python3 bindings
python3-pyside.qtwebkit - Qt 4 WebKit module - Python3 bindings
python3-pyside.qtxml - Qt 4 XML module - Python3 bindings
Com relação aos problemas de instalação, se você tiver repositórios extras instalados, eles podem estar aborrecendo o processo. Certifique-se de que seu apt-cache policy python-pyside seja vagamente parecido com o seguinte:
python-pyside:
Installed: (none)
Candidate: 1.1.2-1ubuntu1
Version table:
1.1.2-1ubuntu1 0
500 http://archive.ubuntu.com/ubuntu/ raring/universe amd64 Packages
Se você tiver fontes extras e elas estiverem fornecendo o candidato e elas não funcionarem, isso interromperá a instalação.