As Herb Simon wrote (in 1971!) "a wealth of information creates a poverty of attention".

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".