So that's what this is all about!
I grabbed this screen shot a while ago when I updated to iPhone OS 3.1. I do that sometimes. See something that strikes me as odd and get a screen shot of it, just in case.
Today I just happened to stumble upon some info that explains the odd, "...verify the update with Apple," that concludes this message:
"Rather than just throw in new local protections, Apple decided that every restore of the device would be verified as being valid and safe by Apple itself.
To do this, during the restore process, users see 'Verifying restore with Apple...', during which time a challenge/response protocol is used between the iPhone and Apple: a 'partial digest' of the firmware files being used is sent to a server, which can then decide to sign off on the result... or not.
Not only does this allow Apple to keep custom firmwares from getting loaded onto the device, but it also allows them to recall existing firmwares by keeping people from restoring to them in the future. To do this they simply would refuse to ever sign, for example, iPhoneOS 3.0 again."
Fascinating! Check out the full article.