i have a 620w power supply with many things hooked up to it, so I am sure a 750w would do
keep in mind that a cheapo power supply will not cut it for anything as it will blow under the stress and maybe take your computer parts with it o_o
as long as you buy a quality power supply to fit your computing needs, it should not be a factor in your problem.
if you are curious on how recent power supplies rank, here is a GREAT review site from "jonnyguru".
http://www.jonnyguru.com/

as for your problem, that is weird. to me it sounds like the card is overheating or dieing as you said. Or it is a software problem with windows, drivers, and or the boxing software. If you are up to it, you can download some temp monitoring and stress testing for your computer and run them while monitoring the temps.
also if you have vista/windows 7, try going through the event logs and see if you have any errors related to the video card, boxing software, or drivers, etc.