How to install listings package in Kubuntu for LaTeX?

I recommend you to use apt-file to search for the package that contains a specific file.

If you invoke

apt-file search listings.sty

you should find the package that contains listings.

On my system it's contained in texlive-latex-recommended that you have already installed.

To play it safe i would execute

texhash

to update latex's directory tree.

If you can't get it working after that i'm pretty sure that something else is wrong.