If it is definately in the Users folder, something may be wrong with the index. Please try re-building the Windows Search Index by going to Start -> Indexing Options -> Advanced -> Rebuild
If you continue to have the problem, check to ensure that Users folder and all sub-directories are being indexed. This is accomplished under Indexing Options. Anything in the application data folders is not indexed to avoid issues.
To perform an "old fashioned" search of the entire drive, simply go to Computer -> C:\ and type in the file name
You will receive a warning that the search may take longer than normal.