Description of problem: "add/remove software" can't be started when using KDE. It's nowhere in the KDE desktop menu. Actual results: "add/remove software" is not in the menu. Expected results: Having somewhere in the menu "add/remove software" available.
You need to install kpackagekit, not gnome-packagekit.