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 in all attempts! It is a feature maybe!