I've seen this problem before and it was a indexing issue with lucene,  try re-indexing

Go to Manage->Site Administration->Manage the Search index

Select all the checkboxes and click ok.