Você recebeu o resultado informado para
apt-get install apt-cache porque não existe um pacote chamado apt-cache .
Os seguintes comandos fazem parte do pacote apt :
apt-cache, apt-cdrom, apt-config, apt-get, apt-key, apt-mark
Cortesia: Centro de software do Ubuntu
Como o apt-get está funcionando para você, o comando apt package e, portanto, apt-cache deve estar instalado em seu sistema. Portanto, não há necessidade de instalá-lo manualmente.
Teste apt-cache show apt para garantir que seu comando apt-cache esteja funcionando.