As I was fixing sendmail in an AWS box, I encountered this error:

Sorry, command-not-found has crashed! Please file a bug report at:
Please include the following information with the report:

command-not-found version: 0.2.44

I went looking for a solution, and this is what worked for me:

export LANGUAGE=en_US.UTF-8
export LANG=en_US.UTF-8
export LC_ALL=en_US.UTF-8
locale-gen en_US.UTF-8
sudo dpkg-reconfigure locales

PS: Note that I was running root for these commands.