I faced this very issue last month when upgrading the CPU in my Compaq notebook (AMD P320 2.1 GHz dual core to AMD N620 2.8 GHz dual core). After the upgrade, I powered on the notebook, and within a couple of minutes it just shut itself right off. I did this a couple more times. Thinking it was a dead CPU, I tore down the laptop again, and discovered that there was about a 1mm air gap between the GPU and the heatsink.
When I did the upgrade, I removed the old GPU thermal pad that was stuck to the heatsink, and rather cavalierly applied Arctic Silver 5, thinking that would do it.
Well, after this epic fail, I could see that the AS5 wasn't enough to bridge the ~1mm gap between the top of the GPU and the copper heat sink surface, so I improvised: I made a heat-conducting shim.
Using a sharp knife, I cut a nice, smooth, flat 3/8" x 7/16" rectangular piece of aluminum off a thick foil casserole baking pan (about 1mm thick) that I had lying around. I cleaned both sides of the the shim with 91% isopropyl alcohol, applied thin, even films of Arctic Silver 5 to it and the heat sink ("staining" it), and to the top surfaces of the GPU & CPU. I reassembled my notebook, powered it on, and I'm good to go.
Temps on the GPU & CPU get no higher than 67°C at 2.8 GHz fully loaded, gaming, etc., which is going to be typical for this class CPU, and in a laptop. 28% speed improvement, all around. Totally worth the effort. But anyway, yeah...maybe try this aluminum shim approach. Or maybe even copper, if you can find it. Even though copper is about 3 times better than aluminum at conducting heat, I don't think the operating temperatures would be drastically lower with it.