This is just plain untrue. Thermal paste aids in heat dissipation by making a better contact area between the CPU and the cooler - starting a computer without paste in place is entirely possible and would probably work just fine for a long time if it was left un-stressed - if the CPU is Intel, it also has built-in thermal protection that operates entirely on it's own regardless of OS or BIOS interaction.
If this was it, he would have been able to start his computer as normal.
Yes, new thermal paste is a good idea, but it is not the problem here.