Um possível motivo para a discrepância é que os pacotes instalados para zlib1g-dev e python são da arquitetura i386, enquanto o sistema básico é outra coisa; provavelmente amd64 (também conhecido como x86_64). A menos que suas dependências de compilação sejam explicitamente marcadas como sendo satisfazíveis por um pacote de uma arquitetura diferente, esses pacotes que você instalou não contam.
A capacidade de instalar pacotes de múltiplas arquiteturas simultaneamente no mesmo host é relativamente nova no mundo Ubuntu / Debian, o que pode ter contribuído para sua confusão. Se isso ajudar, talvez você queira ler o link .