Eu usei o eclipse de remoção do apt-get e, em seguida, o apt-get install eclipse e ele ainda fez a mesma coisa. Eu acabei limpando o Sun JDK e reinstalando o Eclipse e ele instalou o OpenJDK. Tudo funciona novamente.
No entanto, estou um pouco desapontado por não estar funcionando com o Sun JDK. Ah bem. Seja o que for.