Ola
Reinstale (ou instale) seus locales (suporte a idiomas)
Durante a instalação do sistema é possivel que ficou metade Inglês / metade Português, resultando num erro de tradução e consequente "quebra" do pacote command-not-found. (Leia o fim da mensagem de erro)
Após acertar os locales (I18n), pode ser preciso reinstalar o pacote com apt-get install reinstall command-not-found
(Mas acho que só acertando os locales já resolve)
Já tive este erro mas com outro pacote.
[]'s