Success after crying and almost putting a hammer to it...
I *did* set up my iphone to backup onto the iCloud, but wasn't confident I did it correctly. After all, it's not like i could just look into it like a C: drive.
I think I restored the phone twice...
When I did try to install the iphone upgrade, I, too, got the black screen followed by the picture telling me to USB connect to itunes. It was in recovery mode. I got a windows laptop where i had admin privileges and downloaded itunes onto it. Then, I plugged my phone into the laptop and agreed to the phone install/restore when prompted; it did not give me the iCloud option. The phone was restored and working after about 5 minutes, but it was like a brand new phone. I went through the phone's set-up exercises.... and cried...
Then, I UNPLUGGED the phone from the laptop, went to Settings > General > Reset > Erase All Content and Settings... cried some more... After it erased everything, if I recall correctly, it automatically prompted me to set up the iphone again. But this time, there was an iCloud option. (See http://support.apple.com/kb/HT1766, iOS: How to Back Up and Restore Your Content.) (Note, at this point, the phone is also connected to my wi-fi/wireless internet.) Then, I guessed at my xxxxx@me.com ID and it gave me my last several iphone backups and allowed me to choose one. I picked the one from a few days ago just in case the newer backups were of the blank, restored phone. SUCCESS. Everything -- photos, IMs, emails, contacts, apps, Notes, music -- are coming back online though it appears it will take several hours.