C'est apparemment un problème d'incompatitiblité avec les backports d'Ubuntu (j'ai eu le même sujet).
Plus d'infos sur :
https://bugs.launchpad.net/ubuntu/+source/qt4-x11/+bug/227922
La solution très concrète pour revenir à la normale :
1) désinstaller tous les qt4 (notamment libqt4core, libqtgui4 et aussi libqt4-core et libqt4-gui). Cela désinstalle Stellarium également.
2) désactiver le dépôt backport (Synaptics -> dépôts -> mise à jour -> décocher "backport")
3) recharger la liste des paquets
4) réinstaller Stellarium
5) ça marche (en tout cas, "ça a marché chez moi" comme on dit !)
Alexandre