hasta donde se el sim no tiene nada que ver (si bien por el sim el telefono pide la configuracion al operador) cuando la pones manualmente deberia de funcionar. Con todo lo que dices que has hecho y sigue sin funcionar todo apunta a ser problema del telefono, ya descartamos cobertura, configuracion. ICS se me haria raro pues ese problema seria para todos los telefonos ( o al menos para ese modelo del operadors, recuerda que el OTA es mandado por el operador y le meten mucha mano). Las ultimas dos pruebas serian:
1) trata de hacer un reset de fabrica (desde modo recovery, has un respaldo de tus cosas antes) es como volver a instalar ICS desde cero
2) dos y mas agresivo, libera tu telefono e instala una rom personalizada
Saludos