Got this problem too, Ubuntu 12.04.1 with command-not-found 0.2.44
I found that if the chosen locale was not generated first (locale-gen), then it will cause this problem.
Got this problem too, Ubuntu 12.04.1 with command-not-found 0.2.44
I found that if the chosen locale was not generated first (locale-gen), then it will cause this problem.