Se il problema te lo trascini dietro da tanto tempo.... è da prendere in cosiderazione il problema Sim
(quasi che, al cambio Sim, si "trascini" in quella nuova, lo stesso problema. Un po' come succede con i Bancomat....)
Hai provato sul tuo Note 4 a tenere per 24 ore altra Sim?
Controlla se è tutto ok... o se segnala la stessa notifica