On an Ubuntu box, I tried using the locate command to find information about a package and ran into the following error:
mlocate: can not stat () `/var/lib/mlocate/mlocate.db': No such file or directory
The locate program (should) routinely builds a database of files on the box and searches it when we call it. As the error message states, this database appears to be missing thereby leading to the error. Fixing it is as simple as calling:
updatedb
which should build the database.
Hope this helps!