I agree with you Fatman, always re apply new paste when removing these things, I use alcohol swabs that I get from the chemist to clean the surfaces.
I think maybe they should try getting an after market cooler for the CPU as I have never relied on Intels own.
Hopefully its not the CPU at fault or even the board itself, even though they both can be returned if faulty.
Ben.