Don't Bloom filters provide just an illusion of privacy when talking about phone numbers because its easy to iterate through every possible number?
I am not quite sure how the dimensioning of the bloom filter affects the false positive probability. Of course it is easy to iterate through many phone numbers, but at least you can not know for sure if a probed number is actually in the filter or just a false positive, giving means of plausible deniability.
I did not want to imply that there is a perfect zero-knowledge synchronization mechanism for your contact book.
Also, there are approaches to make number registration lookups more secure, e.g. bloom filters: http://en.wikipedia.org/wiki/Bloom_filter
I would expect such an approach from a "secure" app.