В какой-то момент некоторые иконки на Ubuntu 14.04 с KDE 4.13.3 превратились в маленький красный крестик. Чистка кеша иконок KDE не помогала.

В тоже время при установке некторых пакетов apt-get ругалась на кривые скрипты pre/postinstall.

Дело было в кривой ссылке на python. В системе одновременно может быть установлено несколько версий python. В /usr/bin/python лежит символическая ссылка на исполняемый файл. Изначально ссылка указывала на /usr/bin/python2.7, однако для компиляции одной софтины мне понадобилось чтобы по-умолчанию скрипты исполнялись под python3 и я ссылку изменил. В результате в системе отвалились некоторые функции. В частности с иконками. Решение простое:

sudo rm /usr/bin/python
sudo -ln -s /usr/bin/python2.7 /usr/bin/python