Se o iphone não é nacional, não tem mais jeito não.
O desbloqueio foi feito porque o firmware tinha o bootloader antigo, depois que atualizou o bootloader não tem mais jeito, a não ser esperar uma solução dos developers. Mas dizem por aí que nem estão trabalhando nisso ainda, ou seja, pode demorar um bocado.
O que você pode tentar fazer é o downgrade do seu bootloader procurando tutoriais pela net, mas é uma parcela pequena de celulares que são passíveis de downgrade de bootloader, o que dúvido que um iPhone 3GS seja.
Resumindo: a única coisa que você vai conseguir é fazer o jailbreak e usar o iPhone como um iPod touch.... triste, mas é a realidade.
Quanto a isso, faça o seguinte:
- Faça um backup
- Faça uma nova conta em System Preferences > Account
- Logue com ela e sincronize seu iphone com o itunes zerado dela
- Volte para a conta principal e sincronize com seu backup
Deve resolver...