У меня была аналогичная проблема, во время установки eclipse. openjdk-7-jdk требуется, а среди пакетов для установки это не было найдено. Я использовал
> sudo apt-get update
> sudo apt-get install eclipse eclipse-cdt
и нашел openjdk. Я не имею в виду, что вы устанавливаете eclipse, конечно, но этот опыт может оказаться полезным.