В системе остались пакеты от старой версии Krita и они конфликтуют с необходимыми для установки новыми пакетами, apt-get autoremove их не удаляет.
А почему apt-get autoremove должен их удалять? У этой команды вполне определённые условия: удаление того, что поставлено по зависимостям. Если эти библиотеки ставились самостоятельной командой, либо вовсе до появления фичи autoremove, они и не должны удалиться.
Можно было вот так, кстати, сделать:
apt-cache list-extras. Да и нужно наверное. Надо только иметь ввиду, что если что стороннее установлено, то вынесет.