I have the exact same problem! With the same hardware running debian. I even tried switching to the open-source readon driver (mesa 7.12 git) and tweaking the cpu governor.
Right know ,while compiling a custom kernel, the sensors output even reaches 87 and 85 degrees with a load average of 1.72 1.55 1.29
I don't think it is possible to fix this under linux since i have the same problems under windows 7. Of course I can't accurately measure the temp and load under windows but it is just as hot to the touch.
Adapter: Virtual device
temp1: +87.5°C (crit = +100.0°C)
Adapter: PCI adapter
temp1: +85.1°C (high = +70.0°C, crit = +100.0°C)