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.