Comment 3 for bug 561046

Confirmed

Actually this is a bash bug. See /etc/bash.bashrc

# if the command-not-found package is installed, use it
if [ -x /usr/lib/command-not-found -o -x /usr/share/command-not-found ]; then
 function command_not_found_handle {
         # check because c-n-f could've been removed in the meantime
                if [ -x /usr/lib/command-not-found ]; then
     /usr/bin/python /usr/lib/command-not-found -- $1
                   return $?
                elif [ -x /usr/share/command-not-found ]; then
     /usr/bin/python /usr/share/command-not-found -- $1
                   return $?
  else
     return 127
  fi
 }
fi

The second elif case is broken, the directory _still_ exists because command-not-found-data puts some stuff inside. I don't know why the second check exists as the program itself lives in /usr/lib.