The problem (report here) resides in zic, used by the KDE Date and Time module (and other programs), which copies the timezone to /etc/localtime without checking if the original is a symbolic link and therefore, without properly referencing it, por lo que termina creando una liga rota:
ls -l /etc/localtime
lrwxrwxrwx 2 root root 25 mar 14 10:46 /etc/localtime -> ../posix/Europe/Guča
Para arreglarlo temporalmente:
sudo dpkg-reconfigure tzdata
O un paliativo más duradero (y extremo):
sudo mv /usr/sbin/zic /usr/sbin/zic-bad
PuesKDE puede funcionar sin zic (otros programas, quien sabe ;).