Comment 27 for bug 1190696

Facing this issue on Ubuntu 16.04 and looks like the best solution right now is to just uninstall the mlocate package and install the MlocateConflictingPackage (https://github.com/rdiez/Tools/tree/master/MlocateConflictingPackage) to avoid installation of mlocate again due to some updates.