Run into exactly this issue with command-not-found:
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=916783
It is probably due to our umask lockdown.
Workaround:
sudo chmod o+r /var/lib/command-not-found/commands.db*
I am considering to apply that workaround by default, not great, but if this is the only of a very few issues due to umask changes this is ok.