I would say that re-installing Windows is a bit overkill tbh.
Are you using up to date AV and Anti-Spyware software?
Try downloading and running
ccleaner, it will clear out all the unused crap from your PC.
If the problem still persists I would guess that it is a program or service that is taking its time to startup. What do you usually have running in the system tray?