Ok, bobo de mim.
O problema foi meu arquivo /etc/environment . De este tópico , aprendi que a segunda linha:
PATH="/usr/local/texlive/2015/bin/x86_64-linux:$PATH"
foi literalmente interpretado: a variável $PATH não é expandida (como geralmente está em um arquivo .bashrc ).
Usando startx , tive minha sessão aberta, então o PATH definido no .zshrc mascarou o problema.
Mas ainda não descobri o problema das dependências apt.