One more data point:
I set mine to download before I went to bed last night and it said that it would take two hours. Six hours later when I woke up, the iPhone was saying "verifying".
After going out and back in to the Software Update view, it suddenly changed back to saying 1.0.1 was the latest version and no software update was available. Going in and out a few times, it eventually said 2.0 was available and to Download and Install. I thought I'd have to download the entire thing again, but after trying to start it a few times (after entering the passcode it would just drop back to the Software Update screen like nothing had happened), it finally started and went straight to the Preparing step, then installed in about 15 minutes.
So it seems it had downloaded it overnight but failed to prepare and verify it, but kept the download on the iPhone to transfer to the Watch the next time I tried it. All good now and running smoothly!