Eu finalmente consegui consertar meu problema. Parece que foi causado por problemas de PPA para o conjunto de ferramentas do Ubuntu. Eu baixei (do terminal tty) o debian do pacote libstdc ++ 6 para o Xenial no link
No meu caso (amd64) eu fiz o seguinte (em tty, Ctrl + Alt + F1 na tela "error") :
# wget http://security.ubuntu.com/ubuntu/pool/main/g/gcc-5/libstdc++6_5.4.0-6ubuntu1~16.04.4_amd64.deb
# dpkg -i libstdc++6_5.4.0-6ubuntu1~16.04.4_amd64.deb
# reboot
E voilà, isso resolveu o problema:)