Just helped my sister-in-law with the same problem on a replacement iPhone 6 from her carrier in FL. After trying all of the things we found online (like restrictions, reset settings, erase and restore) we finally decided to just dig up the detailed phone info using the IMEI.
IT TURNS OUT OUR US CARRIER GAVE HER A REPLACEMENT PHONE ORIGINALLY FROM SAUDI ARABIA.
If you phone has a model number ending in AE or AB (and there may be others), Facetime will not work.
You can use sndeep.info to run the IMEI and then you can scoll down the page and enter your model number to see the phone's coutnry of origin. You find your phone Model and IMEI in Setting > General > About
Hope this helps somebody out there because couldn't find any info on this exact scenario where a US carrier 'accidentally' issued a refurbished foreign phone.
-