In my opinion, giving out your number, along with the hash of each phone number in your address book to an authority with millions of such hashes isn't appreciably better than giving them in plaintext.
But you wouldn't give out your number. I haven't completely thought it through but the service provider would provide an api for common platforms. All it would do is 2-way encrypt contact numbers (SSL?). Then the service would do a basic lookup using the encrypted data as a key. If there is a hit for this particular platform it'll return the platform specific data (in this case, like a path specific user id).
Of course the other side would be maintaining users in this service, which again is pretty straight forward.
(Hi David?... I'm the OTHER DJB, probably not the one you are thinking of)
(Hi Dan?)