Ho trovato per caso questo thread che assomiglia tanto al tuo problema:
[ame="http://forum.telefonino.net/showthread.php?t=760546"]Carta sim non registrata (Galaxy s e non solo) - Telefonino.net Forum[/ame]
Potrebbe essere veramente un problema di 3 (visto che il cellulare è brandizzato). Vai in un 3 Store e fatti aprire una segnalazione. Di piu non so che dirti.
Ps. Hai fatto l'hard reset? Non devi avere il terminale root-ati per farlo, eh?