The Unity Files Lens currently relies on Zeitgeist to display search results, meaning it can't find files you've never interacted with / accessed. But an improved Unity Files Lens is currently in testing, which doesn't rely solely on Zeitgeist. Finally!
The improved Unity Files Lens is available in a testing PPA for Ubuntu 12.04 Precise Pangolin users. To install it, use the following commands:
sudo add-apt-repository ppa:unity-team/lenses-testing sudo apt-get update sudo apt-get upgrade
Once installed, log out and log back in.
Report any bugs you may find @ Launchpad, mentioning that you're using the Unity Files Lens testing PPA.