I was trying to Jailbreak an iPhone 2G, iPod Touch using redsn0w 0.9 and interestingly enough, had the same issue “stuck at Waiting to reboot” message in redsn0w in both instances. I tried both Mac OS X Leopard and Win XP with no avail.
UPDATE : I faced the same issue with iPhone 3G and 3GS too! Fortunately enough, it has a simple solution.
Solution : When you see the ‘Waiting for reboot’ message in redsn0w, unplug the USB cable from the iPhone and plug it back in! Weird but it worked …