Problem mit der SMS Funktion

[Nummer13]

Ich hab ein seltsames Problem beim SMS schreiben, ich hab seit gestern ein neues Smartphone mit Android 5. Jetzt gibt es Probleme mit dem schreiben von SMS.
Bei vielen Nummern zeigt es an "Nachricht konnte nicht verschickt werden"
Allerdings, bei manchen Nummern funktioniert es.
Insbesondere ins Telekomnetz geht es, in andere Netze nicht.
An der Simkarte kann es nicht liegen, bis gestern (im alten Handy) ging es noch.
Was ich auch schon probiert hab:
Neuanschalten
Simkarte rein und wieder raus
SMS Zentralnummer überprüft
Funktioniert alles nicht.