Executando este comando:
sudo dpkg --confiugre -a
É um bom lugar para começar. Isso garantirá que todas as dependências do tzdata sejam totalmente configuradas e, esperamos, resultem na configuração do tzdata. Se isso não funcionar, poste a saída completa do apt-get para que possamos dar uma olhada mais de perto.