Confira este bug .
Basicamente, você precisará compilar o pyqt porque usar o pyqt empacotado com o python 3 ainda não é suportado, nem mesmo no Ubuntu 11.04 (Natty).O suporte do Python 3 para o Gnome e o KDE é uma prioridade para o Ubuntu 11.10, então, talvez no final deste ano, ele funcionará melhor.
No entanto, pode haver algo especificamente errado desde que você disse que tentou instalar a partir da origem. Talvez a instalação do gole empacotado possa ajudar. Talvez, este e-mail esteja relacionado ao seu problema. Eu acho que você deveria abrir um bug do Ubuntu sobre isso.