or, better still, "find". locate uses a database that yr os updates maybe once a day... so all the results are old. find works like so:
find /path -name "some regex*"
where /path is the directory structure you want to search and "some regex*" is... well, some regex!
that's the uberbasic. believe me, find is insanely powerful. if you need to find all the files owned by root larger than one meg, made before last tuesday, find will do it.