I had a cheap barebone gaming system as seen here
http://www.newegg.com/Product/Product.aspx?Item=N82E16813138178 that i upgraded from a Sempron X2 2200 2.00Ghz 65Watt CPU to a Athlon II x4 620 2.6Ghz 95Watt CPU and had the same problem 4 years ago.
My power supply was weak on initial boot and so it would start to boot and fans would spin at 100% and then after the BIOS splash screen when the Hard Drive was going to load the OS, it would act as if it shut down for a second or two etc with fans shutting off, and then it started back up through the process with fans starting out at 100% speed and would boot with no problems to the OS and games would run fine etc.
What I found was that the CPU upgrade pointed out that the additional 30 watt power draw was too much for the power supply at initial boot, but on a somewhat consecutive warm boot, the system would behave because the voltage rails charged the power supplies internal capacitors up to a higher voltage in which now the load from the HDD was no problem.
I ended up swapping out the ( so called 500watt ) GoldenPower cheap chinese power supply with a cheap but 4 of 5 star rated 460watt Cooler Master and the problem went away. Lots of no name power supplies i have found can not really handle what they are rated for, and are really a marketing mislabeled 250 or 300 watt supply.
If you have a spare healthy power supply available that is at least 400 watts. I'd swap it out and see if the problem goes away. If you have an ultra powerful video card you may need to test with a higher wattage power supply of 500 watts +
If the case was purchased with a free power supply in it, I would highly suggest replacing it with a known good quality brand, as for the cheap no name power supplies can not just fail by causing boot problems, but they can also over voltage components and cook your computer.