Você deve selecionar o modo de recuperação na inicialização, ir até o shell raiz e tentar instalar o pacote ubuntu-desktop
.
sudo apt-get install ubuntu-desktop
Se isso não funcionar, faça backup de dados importantes e reinstale.
Eu não tenho a instalação padrão do Ubuntu, mas para referência, aqui está o que o comando que você usou faz:
~$ sudo apt-get -s autoremove python
[sudo] password for hp:
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following extra packages will be installed:
libpython3.2 python3 python3-minimal python3-uno python3.2 python3.2-minimal
Suggested packages:
python3-doc python3-tk python3.2-doc binfmt-support
The following packages will be REMOVED:
aisleriot apparmor apport apport-gtk aptdaemon apturl apturl-common
autotrash bluez bluez-alsa bluez-gstreamer checkbox checkbox-qt
command-not-found compiz compiz-gnome compiz-plugins-main
compiz-plugins-main-default compizconfig-backend-gconf
compizconfig-settings-manager deja-dup duplicity evolution-data-server
firefox firefox-globalmenu firefox-gnome-support foomatic-db-compressed-ppds
gconf-editor gconf2 gdebi gdebi-core gedit gksu gnome-bluetooth
gnome-control-center gnome-media gnome-menus gnome-orca gnome-sudoku
gnome-terminal gnome-terminal-data gnome-user-share gstreamer0.10-gconf
hplip hplip-data ibus ibus-pinyin ibus-table indicator-datetime
indicator-power intel-microcode jockey-common jockey-gtk
landscape-client-ui-install language-selector-common language-selector-gnome
launchpad-integration libcanberra-gtk-module libcanberra-gtk3-module
libcompizconfig0 libfolks-eds25 libgksu2-0 libgnome-media-profiles-3.0-0
libgnome2-common libgweather-3-0 libgweather-common libmetacity-private0
libpurple-bin libreoffice-gnome light-themes lsb-release metacity
metacity-common microcode.ctl nautilus-share network-manager-gnome
nvidia-common nvidia-settings-304-updates onboard oneconf openprinting-ppds
printer-driver-foo2zjs printer-driver-postscript-hp printer-driver-ptouch
printer-driver-pxljr printer-driver-sag-gdi printer-driver-splix
pybootchartgui python python-appindicator python-apport python-apt
python-apt-common python-aptdaemon python-aptdaemon.gtk3widgets
python-aptdaemon.pkcompat python-brlapi python-cairo python-central
python-chardet python-compizconfig python-configglue python-crypto
python-cups python-cupshelpers python-dateutil python-dbus python-debian
python-debtagshw python-defer python-dirspec python-egenix-mxdatetime
python-egenix-mxtools python-eyed3 python-gconf python-gdbm python-gi
python-gi-cairo python-gnomekeyring python-gnupginterface python-gobject
python-gobject-2 python-gst0.10 python-gtk2 python-httplib2 python-ibus
python-imaging python-keyring python-launchpadlib python-lazr.restfulclient
python-lazr.uri python-libproxy python-libxml2 python-louis python-mako
python-markupsafe python-notify python-oauth python-openssl
python-packagekit python-pam python-pexpect python-piston-mini-client
python-pkg-resources python-problem-report python-protobuf python-pyatspi2
python-pycurl python-pyinotify python-renderpm python-reportlab
python-reportlab-accel python-serial python-simplejson python-smbc
python-software-properties python-speechd python-support python-twisted-bin
python-twisted-core python-twisted-names python-twisted-web
python-ubuntu-sso-client python-ubuntuone-client
python-ubuntuone-storageprotocol python-uno python-virtkey python-wadllib
python-xapian python-xdg python-xkit python-zeitgeist python-zope.interface
rhythmbox rhythmbox-mozilla screen-resolution-extra sessioninstaller
software-center software-center-aptdaemon-plugins software-properties-common
software-properties-gtk system-config-printer-common
system-config-printer-gnome system-config-printer-udev totem totem-mozilla
totem-plugins ubuntu-artwork ubuntu-minimal ubuntu-sso-client
ubuntu-sso-client-gtk ubuntu-standard ubuntu-system-service ubuntuone-client
ubuntuone-installer ufw unattended-upgrades unity unity-2d unity-common
unity-lens-applications update-manager update-manager-core update-notifier
update-notifier-common usb-creator-common usb-creator-gtk xdiagnose
xul-ext-ubufox zeitgeist zeitgeist-core zeitgeist-datahub
The following NEW packages will be installed:
libpython3.2 python3 python3-minimal python3-uno python3.2 python3.2-minimal
0 upgraded, 6 newly installed, 212 to remove and 0 not upgraded.
Observe, por exemplo, que ele remove gnome-terminal
, e é por isso que você não pode iniciá-lo.