Ja wenn es auch mit einem neuen Handy passiert, ist definitiv etwas faul. Haben sie es sowohl mit 079 wie auch mit +4179 versucht? Sollte zwar keine Rolle spielen, aber vielleicht ist tatsächlich ein Tippfehler irgendwo in der Nummer.
Kommt wirklich ein echtes Besetztzeichen (das langsame), oder ist es ein "Gassenbesetzt" (nur 3-4 kurze tüt-tüt-tüt)?
Ich würde mal auf jeden Fall bei Swisscom anrufen oder gleich im Shop vorbei mit beiden Handys, wenn alles nicht hilft.