elasticsearch/elasticsearch — pull request #1953 by Seldaek (2012-05-15 21:08:37+00:00)
Title: Update requirements of the deb package

Virtual packages such as java*-runtime are provided by various java/JRE implementations, which makes it more flexible to use.

Note: I can't say I tested this, but AFAIK it should help. If you can make a test build and link to it on the related ML thread I can try to install it see if it still works with my setup at least.