Eu enfrentei o mesmo problema no debian. lá estava o tz-data e eu o consertei adicionando o repositório point release ao apt e então fiz apt-get update
e apt-get upgrade
. Eu não sei como isso é feito exatamente no Ubuntu (não enfrentei o problema), mas aqui está o link da página Debian