I also had the same search problems, but properly configured with only 1 search performed at a time, and 0 incoming and 1 outgoing connections with a 56k, I was able to return results on everything I typed in. It also helped to have a minimal amount of programs running at the same time.
Now if only I could download the files, hmmm.
Excruciatingly slow if they even start at all. Gnotella really is ahead of it's time - for my connection anyway.
Think I'll be using Wrapster in the meantime.