If the power supply is not outputting good power, the motherboard may refuse to boot up. Fans are rather simple things and will generally work no matter how bad the power they get is, to some extent. As Plumboby said, test the system with another PSU. Testing your current PSU in another computer may also determine if it is a problem.
EDIT: just saw your post. You may be right in that the PSU is just not outputting enough power. The max power a PSU will safely output decreases with time and yours may be on its last legs. Testing another PSU in your main computer will help determine if this is the case.