Given my own personal experiences it is my personal belief that your problem with searching is related to the huge swarm of users coming from napster after it was shutdown. Lots of newbies using connection settings that are detrimental to network operation.

As Yytrium stated, and I agree with him, the problem should work itself out within the next week. As it stands, it seems to be a little better today than it was yesterday, for me at least. Searches are still an issue, but the network congestion is still pretty heavy.

Give it a week. All will be well