a cryptographic hash of a phone number on their server should match a cryptographic hash of a phone number in a contact list on a phone. The app sends the hash to the server, the server looks up users via the hash and responds with user data for matches.
To be honest this should be a third party service, since it sounds like every major social networking app is doing the same exact thing.
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)
To be honest this should be a third party service, since it sounds like every major social networking app is doing the same exact thing.