Search problem/bug

I have a user who can view a Potential if he goes to the Potentials tab, but from the Home tab (or any other tab), if he uses the Search function at the top of the screen, the search results come back with "No matching record(s) found..."

help?