I just went from a 300W PS to a 400W the other day, and my CPU temp has been hovering around 44C or so. I think it was at 46. The new power supply has a fan on the back to exhaust heat, and another one on the opposite side, rpesumably to draw air into the PSU.
My 300W PS was working fine, but I needed to replace a 235W PS for a computer (K6-2/300) I was putting together for my brother in law. Anytime I hear a loud pop and see a bunch of dust suddenly fly out of the power supply's fan, I'd say it needs to be replaced. So I drove over to CompUSA and found I could pay $27 (or was it $28?) for a 250W power supply... or pay $30 for a 400W they had on sale (CompUSA brand, but still). So I bought the 400W, stuck it in my system, and put the 300W in the 300 (@333) system. So now we both have more power supply than we really need, but it's all good.