Isso já significa que você não tem o pacote appmenu-gtk3 instalado em seu computador.
Se você não estiver convencido, tente remover algo que você obviamente sabe que não existe.
Por exemplo,
sudo apt-get remove kinglear
daria a seguinte mensagem de erro:
E: Unable to locate package kinglear