To update dlocate database, run as root:

update-dlocatedb

The content of dlocate database is stale everytime a package is installed or removed/purged and possibly when a package is upgraded or downgraded. In other words: everytime dpkg do its job, usually through apt. While there is already a cron job set to run update-dlocatedb everyday, apt can be configured to run update-dlocatedb everytime it finishes installing, removing/purging, upgrading, or downgrading packages.

/etc/apt/apt.conf.d/99update-dlocatedb:

DPkg::Post-Invoke { 
    "if [ -x /usr/sbin/update-dlocatedb ]; then update-dlocatedb; fi"; 
};