^He most likely did apply paste, but I doubt it was anything good. And metal on metal heat conduction is generally pretty poor. It just seems odd since the fan is working and there, theoretically, isn't anything on just the heatsink that would go bad.
On that line of though, can you try and adjust the retention screws on the heatsink? They may have loosened which may be causing poor contact between the heatspreader and the sink.