The problem you describe is that "smart" address books are actually quite dumb-- they don't understand the context. When you're just trying to call Ted, you don't really care how many mutual friends you have. The solution is actually well-known in the literature for a long time: focus+context (and relatedly overview +details on demand). Show the caller an easy way to get to Ted's number, stat. The rest is just context, which should really only be shown when the user wants to know more about Ted.
Side thought: maybe, what would be useful are phones that guess who you want to call. Instead of the "most recent" list on a phone, maybe you want a "most likely to call now".
And speaking of Google, they have a "Gesture Search" app that I use all the time to find contacts which I don't think will be on the top of the recent calls list. Usually it doesn't take more than one poorly drawn character at the start of someone's name to have them near the top of the result list. Search, don't sort, and all that.
That is a feature that can be disabled, for one.
For two, every address book platform supports partitioning contacts by category. For instance, i'm a member of the HN G+ circle. Those thousands of contacts don't pollute my usual view because my personal contacts are in another book, which I have set as the default view on my phone.
So I'll concede that in this scenario it may simply be a failure of the platform and not Facebook/Address Books in general. But I think my core point stands.
http://blog.databigbang.com/ideas-egont-a-web-orchestration-...
As a perfect example, the first thing I did when I got a smartphone was hook it up to Facebook. Then I discovered a thousand useless Facebook contacts had been downloaded into my address book. Finding people who I actually wanted to call or text became a nightmare.
I recently uninstalled Facebook from my phone because of the whole address book fiasco. I'm back to a simple list of contacts that I know personally - and it's great.
I'm probably just being a Luddite. I want an address book so I can quickly call Ted. Not so I can wade through all my Facebook, Twitter, Google+, LinkedIn, Foursquare, <Insert Social Service> friends while attempting to call Ted.