That actually sounds similar to a problem I have with my laptop. It would almost always freeze up when booting Windows the first couple times (and even when it manages to get into Windows it doesn't function properly - network doesn't work, system behaves abnormally/unstable). I find that I have to let the system "warm up" before it'll run things properly.
It's a rather old laptop with lots of other problems (such as randomn shut-downs) so I'm not sure what the exact issue could be (it just started happening one day). I'm suspecting it's the RAM, GPU, or mobo. I very much doubt it's the hard drive or software since the hard drive is relatively new and reinstalling the OS didn't resolve it (it's definitely a hardware issue).
If you have issues updating the GPU drivers then I suspect it might be the GPU. I would recommend starting there (try swapping with a different GPU if you can - make sure to completely remove the drivers prior). The next thing to try would be the RAM. If that fails then it might be the mobo.