Could be perhaps the GPU voltage is too high? I have an ATI 4670HD desktop card that I OC'ed using RivaTuner. Once I read and exported the BIOS of the card from GPU-z, I could load it up in RivaTuner and noticed that all my voltages were maxed out already (at stock settings), but I could drop them if I wanted to. You could try undervolting the same way (down to the limit of the card's stability under game load) and see what it does to your temps.
Otherwise, a) when you had the heatsink off for your repaste, did you notice if it was making good contact with the chip? I.e. a nice even coat of paste on both HS and chip hen you removed it? Or, b) did you check if your HS/pipe assembly was twisted or otherwise not flat? A bit of lapping of the HS might help to make better contact with the GPU chip (with less trapped air between).
Just thinking out loud. Those CPU temps are rather high for idle (my 2630QM idles at 40C at room temperature, but thats in a G74 with its good cooling system).
--
G74SX-CST1-CBIL, i7 2630QM 2GHz
32GB DDR3 RAM @1333MHz
GTX560M 3GB DDR5 (192 bit)
17.3" LED 1920x1080
Sentelic TP, BIOS 203
Debian Linux Wheezy (Testing) Kernel 3.2, NVIDIA 295.40