It seems like you are missing command-not-found-data, but command-not-found depends on it..
Do you have the most recent version of the packages installed?
$ dpkg -l | grep command-not-found
ii command-not-found 0.2.7 Suggest installation of packages in interact
ii command-not-found-data 0.2.7 Set of data files for command-not-found.
It seems like you are missing command- not-found- data, but command-not-found depends on it..
Do you have the most recent version of the packages installed?
$ dpkg -l | grep command-not-found not-found- data 0.2.7 Set of data files for command-not-found.
ii command-not-found 0.2.7 Suggest installation of packages in interact
ii command-