Non è così improbabile che si verifichi una locale/occasionale incompatibilità tra sim, telefono e celle GSM/UMTS...

A mio avviso si tratta di un'equazione a 3 variabili e pertanto richiede un'analisi separata per ciascuna di esse:
1. Fai una prova con un altro iPhone uguale al tuo e la tua sim girando per Milano e Verona
2. Fai una prova con un altro cellulare UTMS (non iPhone) e la tua stessa sim
3. Prova un'altra simcard del tuo stesso gestore (ma diverso numero) con il tuo iPhone
4. Fatti sostituire la tua simcard e provala sul tuo iPhone
5. Infine prova una sim di altro gestore sul tuo iPhone

Se in tutti questi esperimenti tutto funziona regolarmente allora sei di fronte ad uno di quei casi di incompatibilità complessa che nessun tecnico di rete ammetterà mai poter esistere e che farai una fatica infernale a dimostrare.

Comunque, le reti dei gestori sono fatte a macchie di leopardo e utilizzano tecnologie diverse in zone diverse (ad esempio possono esserci ripetitori Alcatel a Milano ed Ericsson a Verona) il che può creare rarissime locali incompatibilità tra terminale e rete dell'operatore. In passato con le primissime installazioni Omnitel si verificavano spesso fenomeni di questo tipo, ma pensavo appartenessero al passato.

In ogni caso, se una prova prolungata del test numero 1 darà esito positivo (tutto funziona regolarmente) puoi sempre tentare di fartelo sostituire da Apple (ammesso che tu riesca a convincerli).