Sorry, command-not-found has crashed!

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:
https://bugs.launchpad.net/command-not-found/+filebug
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.

Source: http://ivaniliev.com/sorry-command-not-found-has-crashed/