Sorry, command-not-found has crashed!

Whenever typed a command that didn’t exist on some of our servers I got the following:

$ poop
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

It turns out that it was to do with locale settings, I fixed it by

$ sudo locale-gen en_GB.UTF-8
$ sudo update-locale LANG=en_GB.UTF-8