I've seen this problem crop up a few times now so I thought I'd try and share in case you run across it and are trying to troubleshoot. I've seen cases where you can't get name resolution to work, like when you type in a name in the type-in control then click the resolve button. You may even attach a debugger if you've developed a custom claim provider and you see your provider do the right thing, but when all is said and done the name you've typed still has a red squiggly underneath and it says no matches found. What is more telling about this particular problem is that you find that the out of the box providers no longer work either. For example, you can type in NT Authority/All Authenticated Users and it won't be resolvable either.
It turns out what is happening is that some provider, some where, is throwing an exception when its overload of FillResolve is invoked. The particularly troubling thing here, as you may have guessed from the intro, is that it means one bad provider can bring down all name resolution in your farm. So, if you run across this scenario where you can't even get the out of the box providers to resolve names, start looking around for custom providers. You'll probably need to remove them one-by-one to find the problem provider if you haven't written them all. There are other concerns if doing that of course, primarily being that if you add them back in a different order then they won't generate the same underlying claims that they did previously (because part of the claim is based on the order in which the provider was added).
But the main theme here is just what to look for when you have this problem, and how to get rid of it.
IMPORTANT COROLLARY / READ THIS
One thing that the info above hopefully illustrates, is that you all, my good custom claims provider developers, should NOT be throwing exceptions in your providers. If you do, then you risk being the "bad" provider that can prevent name resolution from happening in a farm. And no one wants to be on the other end of that phone call.