I recently had the same problems with my 3GS after updating to the OS4.1 I even came up with a 1604 error and thought I bricked my phone. The solution for my phone was to return to the older firmware. I accomplished this by downloading an older firmware from http://limitededitioniphone.com/where-ca... then I did the following:
Turn off iPhone – Hold down the Sleep/Wake button for a few seconds until the red slider appears, then slide the red slider
Press and hold down the Home button until a yellow triangle with a text which says Please Connect to iTunes appears
Plug the iPhone into my PC (windows)
I already had Itunes running so make sure its on.
iTunes prompted with a message that said iTunes has detected an iPhone in recovery mode. Click OK.
You will be taken to the iPhone pane. Hold down the Shift key (in Windows ) and then click on Restore
The step above will open up a window to allow you to select the firmware software file you would like to use to restore the iPhone. Browse through the folders (Located in my case under C:\Documents and Settings\Oldturkey\Application Data\Apple Computer\iTunes\iPhone Software Updates remember that this is a hidden folder and you may have to unhide it to find it.
Select the old firmware file that you downloaded i.e.iPhone2,1_3.8.1_8B117_Restore.ipsw.
Wait for the full restoration process to complete, and the iPhone will be restored to state based on firmware file you selected.
It does sound complicated but is really not that bad. Hope I got all the steps outlined to follow this. I do not know if this will resolve the issues that you are having with your phone. Also remember with a restore it is very likely that you will loose all your info and music on your phone.Best answer I can give you and I am no expert in this :)