Python Error Message – Why It Appears When Typing Nonsense Commands

Whenever I type any "nonsense" command, this python error message is generated. Normal commands work fine. Any idea how to debug this?

$ somenonexistingcommand
Traceback (most recent call last):
  File "/usr/local/lib/python2.7/site.py", line 553, in <module>
    main()
  File "/usr/local/lib/python2.7/site.py", line 535, in main
    known_paths = addusersitepackages(known_paths)
  File "/usr/local/lib/python2.7/site.py", line 268, in addusersitepackages
    user_site = getusersitepackages()
  File "/usr/local/lib/python2.7/site.py", line 243, in getusersitepackages
    user_base = getuserbase() # this will also set USER_BASE
  File "/usr/local/lib/python2.7/site.py", line 233, in getuserbase
    USER_BASE = get_config_var('userbase')
  File "/usr/local/lib/python2.7/sysconfig.py", line 535, in get_config_var
    return get_config_vars().get(name)
  File "/usr/local/lib/python2.7/sysconfig.py", line 434, in get_config_vars
    _init_posix(_CONFIG_VARS)
  File "/usr/local/lib/python2.7/sysconfig.py", line 298, in _init_posix
    raise IOError(msg)
IOError: invalid Python installation: unable to open /usr/include/python2.7/pyconfig.h (No such file or directory)
$ echo this works fine, however
this works fine, however
$

EDIT – after fixing my /usr/bin/python, I now get this different python error message:

$ yetanothernonexistingcommand
Traceback (most recent call last):
  File "/usr/lib/command-not-found", line 10, in <module>
    import CommandNotFound
ImportError: No module named CommandNotFound

Somehow, python is being run whenever I mistype a command.