My HD 3850 ran in the 80's at full load.
(This will void your warranty, when done correctly can also add to the life of your card.)
If you are not affraid to take the heatsink off. I would advise you to do that. Seems like ATI has gone back to there old self with the TIM and heatsinks. When I took mine off a few days ago, I had no TIM on the GPU. It had been pressed to the side of it and when I felt the heatsink, it was so rough I dont think 40% of it was actually touching the GPU.
I ended up lapping the heatsink very carefully to get the "waves" out of it and made it as smooth as possible without gashing the alum.. After I did that I applied some AS5.
Now my full load temps do not go past 68c and the idle is right around 36c (+/-1c).
I think you will be very suprised and PO when/if you take the heatsink off and odds are you are going to find that to be your heat issue.