OK, so here's an interesting unexpected twist. I had forgotten about the OTA update capabilities of iOS 5 and I started downloading the update on iTunes after it told me an update was available when I plugged in my iPhone. Then I saw this post and decided to unplug my phone and install the update OTA. It worked great. Then about 45 minutes later, my phone went black, rebooted, and showed the 'plug into iTunes' symbol. I thought to myself, 'oh no, what the heck just happened, is the update bad??'
No, the update wasn't bad. I have my phone set to sync wirelessly with my Mac. So it appears that iTunes finished downloading the update on my Mac, then proceeded to continue to install it, albeit wirelessly, on my phone, even though I had already installed it OTA. Now as I am writing this, my phone is in recovery mode and it now seems I have to do a restore. Grrr. I'll post back when I get the phone back up and running...
UPDATE: So the restore is done, now iTunes is copying all my apps, data, music, etc. back to the phone. Sigh. Latest backup was from yesterday, so I lost a little bit of data and a few settings (like password). Apple needs to add an extra check right after the download completes to confirm the device did not get updated (in some other way like OTA during the 800 MB download) before it begins updating the device.