I have a laptop and a desktop with Natty. The laptop does exactly what it's supposed to: I press [super]+f, type the first few letters of a file I want to use (that I have used recently), the results on the lens change to what I want. The desktop is different. Application search works fine, but files & folders does not change whatever I type in - the same most recent files show up on the list.
Solved - while I was typing this up, but I figure someone might appreciate the fix. Delete the Zeigeist database
rm ~/.local/share/zeitgeist -r
Try searching now...