Yeah, sorry mate I don't have any suggestions that don't involve serious work.
It's probably an issue with the heatsink assembly but taking it off, cleaning it and reseating it is not something I'd suggest for an amateur. If it's in warranty send it off for repair, otherwise all I can suggest is try to reapply the thermal interface stuff with some decent thermal paste but you'll probably have lots of thermal pads that will need replacing too. If you're not feeling up to it then a PC repair shop or the manufacturer will attempt repairs at a cost of course.
What temperature is your CPU reaching at idle and under load?