Parece que minha instalação padrão veio com uma versão estranha do Java - não do OpenJDK, mas de outra versão. Eu fiz uma instalação do aptitude para obter o openjdk-7 e então tudo funcionou bem.
Eu estava confuso porque o Eclipse compilado sem um javac no sistema, mas eu acho que o Eclipse tem algumas ferramentas dentro que permitem compilar.