Ну... Вообще тут ты немного загнул, мне кажется. Gdebi давным давно устанавливает все зависимости (имеющиеся в репозиториях) самомстоятельно, естественно, предупреждая об этом пользователя :). Таких проблем в Убунте не помню :). Вот в Дебиан было такое. А ещё там Gdebi сначала устанавливал программу, а потом проверял зависимости :D Потом через Синаптик приходилось удалять установленное, если зависимости удовлетворить неполучается :).

А в Кубунте скорее всего сделают нечто такое же на Qt и всё :).