Eu recomendo que você use apt-file
para procurar o pacote que contém um arquivo específico.
Se você invocar
apt-file search listings.sty
você deve encontrar o pacote que contém listings
.
No meu sistema, ele está em texlive-latex-recommended
que você já instalou.
Para jogar com segurança, eu executaria
texhash
para atualizar a árvore de diretórios do latex.
Se você não conseguir trabalhar depois disso, tenho certeza de que algo está errado.