Se lo hai comprato nuovo e quindi sei sicuro di non avere nessun blocco fatto da un operatore, il problema potrebbe essere hardware e non software.
Il fatto che avvolte funziona e avvolte no mi fa dubitare un problema alla scheda logica...non ti rimane che portarlo in un centro specializzato Samsung o uno tuo di fiducia e se tutto va bene te ne dovresti uscire con una cinquantina di euro