El problema (reporte aquí) reside en zic, usado por el módulo de Fecha y Hora de KDE (y otros programas), que copia la zona horaria a /etc/localtime sin checar si la original es una liga simbólica y por lo tanto, sin dereferenciarla apropiadamente, 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 ;).