I'd say go ahead and open your PSU up. Sure, the capacitors DO hold a powerful charge, so be careful and simply DON'T TOUCH THEM! In fact, try not to touch ANY metal part of the board (the metal case is grounded, so that's OK to touch). Get it open and take some compressed air to it to remove all that dust. I took mine apart to replace the fan one time and ended up with a big pile of dust on the floor, so do this in the basement or garage if possible. Next, you can unscrew the fan and usually disconnect it from the PSU board. Now you can blow out dust and test it (it should just be a 12v 80mm fan, you can plug it into another PSU to test it). If it can't be fixed, you can take another 80mm fan, splice the old fan's connector on (if necessary), and plug the new fan into the PSU board and mount it in the PSU case. As long as you don't touch the metal heatsinks or capacitors, you should be perfectly fine. To be extra careful, let the PSU sit disconnected for a day or so before operating on it (let the capacitors drain a bit).
I've opened many PSU's before, one from an old AT computer (lowered the fan voltage to make it quieter), one from an old Compaq (replaced the noisy fan with a quieter blue LED fan), and one mini-ATX PSU from my HP desktop (wanted to see if I could re-route the wires, but I couldn't, so had to get a new PSU).