With my HD 5870, I also started experiencing higher temps than normal with it. Turned out the thermal compound had wore out over the years. I cleaned off the old stuff and applied new compound. Dropped my temps back to a normal range.
That being said, blow out the dust, make sure the fan is still functioning, and try re-applying new thermal paste.
Good luck.