But if you fail a Circles test the story must goes somewhere fun. Why they think a failed Circles test is not fun? Why they should to overcome the new problems before they can get back to the “good stuff”? Sucess or failure doesn’t matter. Every single roll should lead to good story moments and new interesting situations, IMO.
Forget Circles. Almost everything is about fiction. If a character wants to find some dude, well, make a Circles test then. And if the player fails the roll be sure a lot of fun things happen because of it. Remember the Lando Calrissian thing mentioned above.
One thing that’s gone unsaid is that the story should go somewhere fun. If you know the players hate trying Circles and getting obstructive, obstreperous NPCs, don’t give them those! Give them NPCs who can help in exchange for future favors promised to seedy organizations, or in exchange for dealing with a racist, obnoxious jerk, or whatever else they do enjoy. Give 'em the story they want to be part of, and if they react negatively, change what you’re doing. You can even say that upfront: if they seem down on Circles because the results are always what they don’t like, promise to stop giving them enemies and problems. NPCs who themselves need help before they can be helpful, who demand high payment, or who won’t be back until the very last second, throwing the time-sensitive outcome into doubt, are all ways to make the NPC helpful, friendly, and still not exactly what they were hoping for.
Another trick I’ve tried, which I wouldn’t use all the time but do pull sometimes, is to make the help offered by failure the knowledge that they’re looking in the wrong place. Fail Circles to get the historian who can translate the ancient tome from Old Gibberish and he’ll put on his spectacles, read, take them off, and inform you that the book is encrypted, and they’re going to need a good cryptographer to break the cypher before they can get anywhere with Old Gibberish. Or they find the watch captain who informs them that the matter has already proceeded to the magistrates and they should have spoken to him yesterday.
I might be misremembering (no book on hand, and this might have changed in BWG, which I don’t have), but I think that there is a +1 bonus to Circling a previously Circled named NPC (if you specifically declare that’s who you’re looking for). Additionally, once they have been Circled enough times, they turn into a permament Relationship (which can be accessed without any tests).
So it’s not like testing Circles never ends - at some point you won’t have to look up that particular priest/amoursmith/courtier/whatnot. The key would be to make sure that the same NPCs appear in many situations and are useful in many ways.
Also, I think that Reputations can be used as bonuses to Circles rolls. This should especially help the adventurers with low Circles, but many exploits. They can be voted on or given out by the GM. Small, local reputations might be easy to come by and be helpful. Instead of “a knight who is disposed to help me now” the adventurers might look for “a knight who has heard of my [insert heroic deed committed near the knight’s particular city] and was impressed enough to help me now”.