I spent close to two hours on the phone with a Apple tech who was nice to work with. However, the out come was not that great. A key question he asked me was if I downloaded the OS4 via a wireless connection. I had. He stated that most the people having problems with the phone not backing up, getting into a loop was due to problems with the wireless briefly cutting out during a download. Why Apple does not have a pop up window that states you should not download on wireless is beyond reasoning since now they know it is an issue for many users. Talk about putting your head in the sand.
http://support.apple.com/kb/HT1808 this link will show you how to recover your phone. As soon as your iTunes 9 shows your phone in the devices tab to the left of the screen in iTunes; click on the iPhone icon. The first tab that should pop up is Summary. Scroll down to Version and click Restore. DO NOT restore from your backup because it will not work with the new OS4 you have on your phone. You will have to restore as a new phone. (I know - it is painful - I agree with most of the thoughts flying through your head)
The Apple tech stated anyone can call them and receive free support via a phone to help walk them through the process to fix their phone like he did me. You do NOT have to have apple care for your iPhone to receive the support because the issue is with OS4 which is a problem they created. He was extremely nice about it.
He also stated there was no way to go from OS4 back to 3. The back up feature on iTunes will not help restore contacts, items in my note pad, calendar, as well as my close to 800 photos were all deleted with the upgrade to OS4. The Apple tech did spend about 30 mins on the phone with me showing me how the backup feature for photos work with iPhotos and and the iPhone with OS4. It is a great improvement over the previous way I had to back up on Windows with my PC.
All of my applications came back up on my phone with the restore. However, all the data was wiped on them that had been stored. I read on these Apple Discussion boards where some users were upset that their applications did not come back and they were going to have to repurchase them. This is NOT true. You do not have to repay for them. You go to purchase them as you did the first time, but when it gets time to pay, a window will pop up stating you have already purchased and do you want to proceed. Click yes. The application will download and you will NOT be charged a second time.
As far as my contacts, notes, and photos of my family & friends I have taken for the past 13 months..... all gone. I am in tears over the photos. I'm paying definitely the stupid tax for not backing them up and have learned a lesson. I will also never break the cardinal rule again and end up on the bleeding edge of downloading a new update until several weeks later so all the kinks are worked out.