Comment 2 for bug 1173010

I just had the same issue, but re-installing command-not-found didn't solve the issue. Have you been messing around with multiple Python interpreter versions by any chance?

I had to install Python 2.6 for a certain project to compile from the Deadsnakes PPA and pointed /usr/bin/python to it. That's when I first started having these issues.

Reverting /usr/bin/python back to the previous interpreter immediately fixed the issue.