For those who don't wish to fool around in the Terminal, the solution for me appeared to be "wait a bit."
I got the same error as everyone else attempting to upgrade my iPhone 4 (running 4.3.5) to iOS 5. After two unsuccessful attempts, I waited an hour on the assumption that heavy server traffic was making the "verification" step unable to complete.
Sure enough, the third time was the charm. I made sure not to engage in any other bandwidth-using activities while the update was being downloaded, and that appears to have solved the problem. I'm now running iOS 5.
It may not solve everyone's problem, but I'm not surprised that a little patience turned out to be the key for me.