If you get that password message (assuming you are restoring due to a lost password), it means your iPhone unexpectedly exited the recovery mode before iTunes could download updates and start installing on your phone. When you notice your phone suddenly leave recovery mode and reboot while updates are still downloading, press and hold both buttons again and wait for it to re-enter recovery mode. iTunes will prompt you to restore again, but the download will continue from where it left off. This happened 3 times during one restore of a 3GS, and it's probably due to an automatic recovery mode time-out in phones that are password protected.