А если запустить gdebi-kde через терминал и посмотреть....может напишет чего он так. О KDE ничего не скажу, и вроде с подобным не сталкивался но... можно попробовать поставить deb в котором на 100% уверен что совместим с версией ОС. Еще gdebi ругается когда запущен синаптик....
Еще вариант
dpkg -i /home/user/пакеты/name.deb