Comigo aconteceu o mesmo problema. Fiz o downgrade para a versão 4.3.5 e continuou a mesma coisa. Só tinha salvo o shsh dessa versão. Fiz até desbloqueio pelo redsnow e nada.
Meu Iphone 4 tem o selo da anatel, porém, não sei se ele tava desbloqueado via operadora.
Testei chip Tim e Claro e ficaram com a barra zerada, a Oi nem isso, ficou "sem serviço" total!
Cheguei até a mandar uma reclamação pra Anatel da Tim e Claro, já tem bem uns 4 dias e não obtive nenhuma resposta.
Não sei mais o que fazer a não ser esperar, esperar até que alguém apareça com alguma solução definitiva para esse problema.