If you removed the heatsink fan from the laptop you should have put on some new thermal paste. You didn't mention that you did so I assume that you didn't. Perhaps since you didn't the cpu heats up way too fast to allow Realtemp to measure it correctly.
How long does it take before it shuts down the first time? Each time thereafter? If it's a heating problem it generally lasts longer turned on on the first boot. IT usually lasts less each time thereafter.
Any blue screen? Any other performance issues? If you are having other issues it would be a good idea to post them on here so that way the culprit is found faster.
I didn't have to remove the heatsink to get to it and see that it wasn't dusty and that the fan is working, although I do have thermal paste if I decide remounting it is something I should try.
For some reason, after reassembling and putting my laptop back together I haven't had it turn off since my initial post. I'm using it now. Temperatures are staying around 50C during web browsing and word processing. Yesterday, this was happening repeatedly and never staying on longer than a minute or two.
Everything seems fine now, but before I did anything the computer would boot all the way up (slower than normal) and then shut off about the time you try to launch a program.
In my experience, computers only abruptly shut off whenever a fan isn't working or mounted correctly, or when they overheat past 90C, or when I poor Diet Pepsi onto them.