Any chance its a 17" laptop? If so, it could be overheating and getting a cooler pad could really help it operate at a cooler temp. My Fiancee's laptop was just doing this, took forever to boot and shut down randomly without warning. A large cooler pad fixed it and now it runs at a nice cool 50C.

If it isn't a 17", what brand and how old?