New thermal paste as well as clean out the dust and make sure the fan is working.

If it uses a heatpipe cooling system, it is possible the heatpipe has leaked and is no longer working.

If it feels hot to the touch it doesn't really mean that it needs new thermal paste, the fan could be at fault (old grease that dried up over time or accumulation of dust). I have a Fujitsu Siemens with a Pentium M which gets stupidly hot underneath and a Acer with another Pentium M which is cool to the touch, both under load, working fans and fresh thermal goo. I also had a Latitude C600 with a Mobile Pentium III, which ran pretty hot as well.

I would check the CPU. It might have made due up till now with a thermal pad sitting between the CPU and the metal chassis or some other form of passive heatsink, and this connection might be loosened due to the thermal pad disintegrating. The Coppermine should ramp up its temp when under constant load, albeit should sit quite cool at idle under Windows.