Is it reasonable to trust for me to trust you to you run some arbitrary binary on my phone that does some magical black box computation on my contact list and then phone home to your service, but not trust to that you will just not be a dick with the raw data?
Stated more simply, if I am paranoid about my privacy, then why am I running your apps and letting you read my contact list at all?
The problem with how snapchat failed isn't so much that they weren't storing the information securely but that they had absolutely no gate on getting the information aside from a global api key. If you're running their app you've already exposed the phone numbers and are trusting them not to be too evil with them.
My expectation as a user of their service (I'm not, but if I were, and this applies to things like facebook as well, of which I am a user) is that they won't tell people I don't want to know who I am and if I'm using their service.
To this end what's needed is that before it gives another user a positive result (especially tied to my name) to my phone number it should have a reasonable expectation that I want them to have it. If they store the information that lets them derive this expectation in a way that keeps my info secure, that is also fantastic, but it's a second tier concern to becoming literally the whitepages by accident.
The problem is that an application requests your contacts, uploads them to their server, and then who knows what they do with that information afterwards; maybe they store it, perhaps later that database is leaked, or they sell the stored information in the future.
If you trust the service you're using fully (you trust the server will not be compromised, the owners of the servers will not cave to demands to store/release data, the owners will not be malicious with your data) then this isn't a problem at all. Transmit the raw data over SSL then perform the checks and do not store the data.
Like it or not, people do overtrust companies like snapchat. We need to change that too.
But in the mean time, snapchat's biggest and first mistake was to leave their database an open book without even having to compromise their service or servers. The people who did this used nothing that their client application doesn't use every day, and that is not an unsolvable problem at all. It's no different a problem than every single social network already has to solve, whether their users trust them to encrypt or otherwise obscure their data once obtained or not.
But what you are saying is like looking at football players, seeing that they could still get hurt when they wear lots of padding, and deciding either no one should play the game or we should all play inside giant airbags.
The second question I haven't seen asked here yet, is why we need everything to be social to start with? My social needs are covered by Facebook and Twitter, and I don't install their apps on my phone either.
Given those two things, if an app (any app!) requires access to my contacts I don't install it. Period.