tzdata-java
foi removido porque o OpenJDK 8 não fornece os arquivos necessários para criá-lo. Citando o relatório de erros do Debian que solicitou sua remoção:
O problema é que o java padrão foi recentemente alterado para openjdk-8, que não fornece o javazic.jar. Como tal, não podemos mais construir o tzdata-java.
A outra outra resposta fornece um PPA que fornece um pacote Xenial tzdata-java
para o OpenJDK 6 e 7.