Na verdade, o pacote tzdata mais recente contém os dados corretos do fuso horário. Para instalá-lo manualmente, fiz isso:
wget http://archive.ubuntu.com/ubuntu/pool/main/t/tzdata/tzdata_2013d-1ubuntu1_all.deb
sudo dpkg -i tzdata_2013d-1ubuntu1_all.deb