Right now I've got a T500 (Thinkpad/Lenovo) and It's idle temperatures are around 90C. Its got a ATI Mobility FireGL V5700 GPU. I've overclocked it from 600/700Mhz to 700/855Mhz. However, even when I underclock my laptop, its still uber hot.
Well the fans are fully functional and now its at 100C at idle I'm using the AMD GPU clock tool to find out temperatures; It says ASIC temperature via internal TSS, which I have no idea what it means. so I think its GPU thats that high. Also Its the left side, right next to the vent. Its just been going on since yesterday I think.
You could try and put some new thermal paste on.
OR turn down the clock back to defaults and monitor the heat. - If you find after turning down the clock speed its still hotter than the sun, put some new thermal paste and try again.