From my computer experience, This sounds like it definitely was heat related. My laptop acted very simular to what you are describing. Cold boots would last about 3 minutes and not so cold boots would just freeze mid-stream.
In the case of the laptop, it turned out to be the voltage regulator card(power card). $15 later from ebay and my own labor, my problem was solved. A heat surge due to dust build up was the root cause in my case.
Curious! What might have caused your problem with it being brand new. Oviously it was a defect. This would indicate a potential recall if it is more wide spread. I am glad you are able to get it replaced.
I know how HR can be at times. It's like pulling teeth to get anything accomplished in a timely manner.
