The wife and I used to be able to facetime between California, USA and Germany. I use an iphone 4 and the wife has both an iphone 4S and a 5s. We also have ipads. The devices can locate the other user, but "call failed" is the common error. We are both on a fast network. I wouldn't think that it makes a difference because I am on a network, but I have verizon. The wife has verizon on the 4 and tmobile on the 5s. Some site said to turn off phone after selecting airplane mode and then restart to correct this problem. It didn't help. Has anyone else had this problem?