During a Windows 7 installation I noticed every step, including “Setup is starting”, would take minutes to complete.
After I while I found that in the BIOS a setting was present that showed my machine to have a Floppy A: drive – which is not the case.
I disabled the A drive in the BIOS and afterwards Windows 7 Setup was fast again.
Hope it helps – let me know if it does in your case!