Ok, eu instalei o eclipse através do apt-get em uma instalação "relativamente" limpa do Ubuntu 13.04 e experimentei o problema referenciado neste tópico quando tentei adicionar o cdt (também através do apt-get). Eu tentei várias coisas para resolver o problema, reinstalado repetidamente.
Antes de corrigi-lo, fiz o seguinte para alternar de openjdk para oracle java, o que pode ou não ser relevante:
sudo apt-get purge openjdk*
sudo rm /var/lib/dpkg/info/oracle-java7-installer*
sudo apt-get purge oracle-java7-installer*
sudo rm /etc/apt/sources.list.d/*java*
sudo apt-get update
sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java7-installer
O que eventualmente funcionou para mim foi:
sudo apt-get install eclipse eclipse-cdt g++
rm -rf ~/.eclipse
rm -rf ~/workspace
eclipse -clean &
Observação: não tive nenhum trabalho real no meu espaço de trabalho. Se fizer isso, você deve fazer o backup antes de fazer algo tão drástico quanto removê-lo.