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.