Try the fixes in this link, different ones have worked for lots of people: http://www.gnutellaforums.com/336823-post2.html

Otherwise, run the condi program & send the info off to mrogers... the developers are trying to work out why some people have this problem with searches.