man i just read this post i wrote and its yet another book. apologies in advance. your ps3 doesn't have the symptoms of a broken fan (its not actually getting hot to the touch) this sounds like a breakdown of the thermal paste, however you have said you did that however i assume you didn't remove the heat-plates on each chip?
i suspect the thermal paste and thermal adhesive between the heat-plates and the chips need replaced, and i would also recommend a flux based re-flow and perhaps even a shim trick as well (the 60gb orig gets the hottest of all the versions of ps3 so anything to reduce the heat will help, its just a matter of how much time work and cash your willing to throw at it).
i will say this your very lucky it didn't stay ylod on you as that's what usually happens. my current ps3 is on the shelf right now after its 11th ylod and that's AFTER cooling mods, re-flows with flux and carving of the casing were applied. the only mods left to do now are the extreme heat-plates and shims tricks. (i know what's overheating this time - its the memory chips, i know this because the thermal tape had bubbled.
i'm not sure it can be fixed this time so im throwing the kitchen sink at it) anyway enough about mines - run the latest multi-man, the one with the temp monitor and use it and track the temps before it shuts down and you may be able to find out if it is in fact what i suspect. if its not that, it is perhaps the psu but try the easy stuff first.