While trying to upgrade my iPhone 3G from iOS 4.0 to iOS 4.0.1 it simply got stuck on “waiting for iphone” step on iTunes for 
The solution is simple, just RESTART your computer and it should fix it.
Other people proposed like taking out sim card, using other sim port or other computer or turning off the apple mobile device service (which is logical to the restart process too).
Hopefully now when you retry the procedure of upgrading / restoring your iPhone firmware it will not stuck on the waiting for the iPhone step on iTunes.