iPhone 4S ausgehende anrufe gehen nicht

Hallo, ich habe ein 4S und folgendes Problem: "Ich kann niemanden Anrufen." Anzeige direkt: "Anruf fehlgeschlagen."
Ich war in Deutschland und hatte ne deutsche SIM drin (wie immer mit demselben Telefon, noch nie hatte ich dieses Problem). Als ich zurückkam hab ich direkt wieder meine alte SIM eingesetzt (wie immer). Ich kann weder mit der deutschen Nummer, noch mit der jetzigen noch mit einer anderen SIM nach außen telefonieren. Im August war ich auch im Ausland, ich hatte noch nie solch ein Problem. An der SIM liegt es nicht, in allen anderen Telefonen (auch andere Apple Geräte, funktioniert es ohne Probleme.
Das witzige ist, SMS kann ich Schreiben und Empfangen und auch Anrufe kann ich entgegennehmen.
Da es nicht funktionierte hab ich mein Telefon auf Werkseinstellung zurückgesetzt, nun schon zum 3. mal und es geht noch immer nicht. Der Rest funktioniert einwandfrei.
Egal welche SIM ich bei mir einsetze, bei allen dasselbe Problem. Telefon ist auf IOS 8.1.
Kann mir jemand helfen?