Executar:
sudo dpkg -r tzdata
Se for bem-sucedido ou não, execute:
gksudo gedit /var/lib/dpkg/status
No Gedit resultante, remover toda a seção começa com:
Package : tzdata
salve o arquivo e feche.
Em seguida, execute seu comando.