Não é possível instalar o mas python-qt4 porque os pacotes libqt4 * não são encontrados nos repositórios.
Meu palpite é que você está perdendo um dos repositórios canônicos, então, por favor, abra Software Sources e na aba Ubuntu Software certifique-se de que ele esteja definido como:
Depois de alterar a configuração, certifique-se de executar sudo apt-get update
. Você está pronto para tentar novamente a instalação.