Eu tive o mesmo problema que foi resolvido seguindo estas instruções da página de instaladores qgis:
Via ubuntugis:
O projeto ubuntugis fornece versões mais recentes de vários pacotes FOSSGIS, sendo o QGIS um deles.
Pacotes atuais disponíveis para precisão e atrevimento.
Se você quiser usar esses pacotes, remova as http://qgis.org/debian
linhas do seu /etc/apt/sources.list
e atualize as dependências atualizadas digitando:
sudo apt-get install python-software-properties
sudo add-apt-repository ppa:ubuntugis/ubuntugis-unstable
sudo apt-get update
sudo apt-get install qgis python-qgis qgis-plugin-grass
Isso funcionou perfeitamente para mim. Boa sorte!