Adding to the chorus here: check the fan.
What I would do is try to first rule out a software-related failure: when the machine boots up, can you hear the fan spinning underneath the keyboard? You could also try another utility like smcFanControl to see if it has any effect on the fans. If other fan apps return a value of 0 for the rpms, it's more likely to be hardware failure (either due to blockages with the fans, or the fans themselves dying).
The definitive way to test out the fans would be to remove the topcase, and jump start the Mac using the
power pads on the motherboard. You should be able to visually see the fans spin up. If the fans run despite SMC/fan control apps reporting a value of 0 rpm, then there's probably a sensor issue. Either if they run, or if they don't, you will still need to replace the fan.
Edit: One other thing you might want to try is to reseat the fan connectors. Good luck, and let us know how it goes.