Just did some testing of the 'locate' command in both Ubuntu 12.04 and
Kubuntu 12.04 - they are *very* different, with the Kubuntu one being
much more flexible !!

What I did find was that in Ubuntu it only looks for files ending in
whatever you search for unless you put a * before and/or after. E.G. I
have a text file with a double ee in the middle of the name.

locate ee.txt finds nothing
locate *ee.txt finds nothing
locate ee*.txt finds nothing
locate *ee*.txt finds it

So if you are finding loads of results do you have many files with
names ending in 'ee' ?