Comment 21 for bug 281471

May be some some system groups change gid during system upgrade. In this case mlocate created before upgrade retains old gid and loses ability to read mlocate.db. I have access to several hosts and mlocate group have different gid there. Of course it does not explain what removes sgid.

Possible workaround is to reinstall mlocate package:

sudo aptitude resintall mlocate