You didn't tell us which cpu you had, but if you are running an i5 or i7 then the mobo and cpu still have some life left; they were never weak cpu and are still pretty powerful.
So, I would look at a new graphics card. OR, if you are afraid of fan failure and toasting the card, find a replacement fan (my son found one for his 5870 on, I think ebay, for $10) and take the card apart and fix it; while it's apart, clean it up really good.
If you want a new card, the R9 series has pretty good prices and models.