Eu finalmente descobri a causa raiz, então eu colocarei aqui caso alguém encontre isso.
De alguma forma, o repositório lucid-updates foi desativado por engano depois que algumas atualizações foram instaladas no processo de configuração do sistema. Isso significa que o pacote tzdata-java necessário não pôde mais ser encontrado, e a versão que pode ser encontrada era muito antiga para ser instalada corretamente.
Eu descobri o problema usando a ferramenta apt-show-versions:
$ apt-show-versions tzdata
tzdata 2012e-0ubuntu0.10.04 newer than version in archive