Te recomiendo hagas lo siguiente:
1. Crea tu Propio Firmware con el sn0wbreeze 2.73.. es importante sepas si tu 3GS tiene OLD bootroom o NEW, lo sabes?.... Crea tu CostumFW usando la opcion "Baseband Preservation Mode"...
2. Pon en Modo DFU el iPhone siguiendo las instrucciones del sn0wbreeze..
3. Prueba de nuevo Restaurar el iPhone, ahora con el CFW generado .... si te diera de nuevo error, bajate el iREB-r4 y ponlo en modo DFU con la ayuda de este..
4. Cuando hayas restaurado el iPhone te dira no tienes un SIM valido para activarlo y es tiempo de utilizar redsn0w 0.9.6rc16 para hacktivarlo... antes de correrlo cierra itunes pero sin expulsar el iPhone.. inicia el redsn0w y sigue los pasos correspondiente.. en las opciones que sigue solo selecciona "install cydia", dale Next y deja que haga su trabajo...
5. Eso deberia ser todo, se reiniciara tu iPhone y ya endras acceso a todas sus funciones menos el telefono, conectado en una Red WiFi abre cydia e instala ultrasn0w para poderlo ocupar con SIM de tu preferencia..
Si apareciera cualquier otro error en itunes notifica que numero te da, cualquier otro problema detallalo lo mas posible a ver que solucion se le puede dar