Eu não sabia que o ubuntu já vinha com o xterm instalado por padrão nessas novas versões, mas também não o uso desde a versão 11.04 e acostumado nos kubuntu e xubuntu que não vem, por isso sugeri a central de programas do ubuntu.
excusas pela gafe.
Não foi gafe nenhuma e sua sugestão foi boa, vale sim a pena fazer o que você sugeriu, primeiro remover completamente pelo Synaptic, atualizar e reinstalar, para ver o que dá.
Algumas soluções indicam problemas no Compiz e dizem para reinstalar, mas acho um tanto quanto radical partir para isso, pode destruir o sistema inteiro.
Vamos ver primeiro se dá para resolver de uma forma mais "light"