> namely reconstructing my call history with everyone that has the facebook app installed

IANAL, but I think that would be okay, as long as they don't associate any/strip all personal identifiable information from your phone number, and don't store the phone number in plaintext.