Might be a good time to check whether the power supply is any good at all. If it's a lightweight cheapie, I'd rather toss it and install a quality new one (80+ certified, yadda yadda). Of course that assumes a reasonably modern computer that's heavy on +12V, not an oldie with CPU power from +5V.
80 mm fans normally last a fairly long time, definitely so if temperature controlled. A PSU that doesn't have a temperature-controlled fan is either very old (>10 years) or cheap trash.
And yes, it's a good idea to remove mains power a few minutes (at least) before opening a PSU. They normally have bleed-off resistors so the high voltages will go down relatively quickly, but still better safe than sorry. DC voltage after the primary-side rectifier can be up to about 385 V, so the filter capacitor can bite quite a bit.