У меня тоже Kubuntu 8.04, как обычно .deb пакеты нормально устанавливаються одним кликом по нему. Вот только, что skype-debian_2.0.0.68-1_i386.deb поставил! Пакет gdebi у меня не установлен, но gdebi-core и gdebi-kde стоят, проверь в Adept Manager и установи если необходимо (правая кнопка ->Request Install потом Apply Changes)!
Возможно проблема из-за "нового" KDE4 (зря рискнул, имхо), можешь сделать и как написали выше.