Un amigo me comentó exactamente el mismo problema, y es que resulta que tenía los repositorios de XGL activados. En estos repositorios publicaron la versión 0.13 de la librería libvte4, entre otras, mientras que Ubuntu lleva la 0.12.
Para que nos entendamos el problema está en que habeis corrompido vuestra instalación con paquetes de repositorios no oficiales.
La solución es abir el archivo /etc/apt/sources.list y dejar solamente los repositorios oficiales, entonces:
sudo aptitude uppdate
sudo aptitude remove libvte4
Os avisará de que lo que va a hacer es desactualizar la librería libvte4 entre otras, y dejarlo todo con las versiones originales. Después de esto, todo volverá a la normalidad.
Espero que os sirva