Ok, I posted this earlier in this discussion and in other topics, but never saw any replies, so I'll post it again. The following instructions are very time consuming (up to 2 hours or more in some cases), requires erasing your phone (so save anything important, and DO NOT rely on the iTunes backup for retrieving the data), and only work on Macs (I don't know or have Windoze procedures for this).
1. Plug in your iPhone to an AC outlet (not your computer) and go to Settings>General>Reset>Erase All Content and Settings. This will take some time. It will also take the phone back to factory settings, just as it was when it came out of the box, so if you have a 3G, that will most likely mean OS 2.x. Once you've started this process, set the phone aside.
2. On your Mac, navigate to your Home folder Mac HD>Users>Your Home Folder, from there navigate to Library>iTunes>iPhone Software Updates. In there you will see a file who's name will be SIMILAR to iPhone1,2
3.1_7C144Restore.ipsw. Move this file to the trash and delete it.
3. Once your phone has completed the erase/reset process, connect it to your Mac. When iTunes opens and your phone shows up, click the "Check for update" button. This will download a NEW copy of the 3.1 update from Apples servers.
4. Once the download is complete and iTunes has updated your phone with the fresh copy of the 3.1 update you've just downloaded, it will be time to set up your phone. DO NOT RESTORE FROM BACKUP!!!! Restoring from backup will most likely restore the problem you're trying to get rid of! Now, when iTunes gives you the option, you want to SET UP AS A NEW PHONE. Once that is complete, re-sync your data. Again, NOT FROM BACKUP.
This has resolved many issues for
most of the people that used this restore method, but it's not a guarantee. The reason behind these steps is that performing a basic restore does not remove the 3.1 firmware currently installed on your phone, which may have been corrupted during the installation nor does it remove the copy of the 3.1 firmware package on your Mac which may also have been corrupted during the download. Further reasoning behind this is that these steps take your phone back to a 2.x version of iPhone OS (if you have a 3G), and you'll be upgrading from 2.x directly to 3.1, bypassing all of the incremental updates in between (2.1, 2.2, 2.2.1, 3.0, 3.0.1, etc...). If someone has success with this (I did after problems when moving up from 2.2.1 to 3.0), please report back so that others will feel more comfortable performing such a daunting task.
G