Comment 9 for bug 1192890

This problem is probably related to:
https://bugs.launchpad.net/command-not-found/+bug/1480388

In that case a simple solution is to change a line in /usr/lib/command-not-found from:

os.execvp("python3", [sys.argv[0]] + sys.argv)

to:

os.execvp("/usr/bin/python3", [sys.argv[0]] + sys.argv)