well, how easy it is to fit a psu all depends on what type of case you haves, so please place that in here somewhere, chances are the new gpu uses more power not because of the fan but because it is a better card, and if the pc WILL start and stay on then i doubt that it is the psu because if it was the pc should turn on and then shut down when under load, as well please post your system specs or add then to your profile and set them to display as most people here have. just my 2c but i think it may be a compatibility issue with the video card, also could you please tell us what type of psu, check the side of it's box, thanks, i will try to help once i have more info

OK my specs are,

psu-Magna ATX 600W
1gb ram
AMD Sempron Processor 3300+ 2.01 Ghz
Micro-star international K8N Neo mother board
Nvidia GeForce 7600 gs graphics card
Windows XP home sevice pack 2

Also I just remembered that the PC turned off by itself during a thunder storm about 1 month ago and this may have been when this problem started but I can't be sure. I did'nt realise that you should not have a PC that is plugged into broadband turned on during a storm. I was using no surge protector.

Could this have damaged the psu?

it could have, but much more likely damaged the motherboard, as for the psu it should be enough for your pc, although, from what i have found and read, the magna psu is not very stable in the 12v rail, it drops below the 12v, so this *MAY* be your problem, or it could also be the motherboard. if you can borrow a psu that is not a cheap, generic one and test it you should be able to determine whether it is that or the mobo.

Just keep the psu in mind for the next time you do a full overhaul, it is one of the most important, but most overlooked parts of the pc, just read a few reviews on the internet.

if it is the mobo, you will need a new one, but i doubt that it would be, also, if you psu has any type of surge protections it should have killed itself to save your pc so it may be damaged, but since your pc isnt failing i doubt that also, try a different psu, or you could just buy one from a well known brand like thermaltake and antec, and just keep it for another upgrade anyway, even if it doesnt solve your problem

of course the solution is all up to you and depends on yourbudget, but i would recommend borrowing one first, or you could take it into a pc store, they should be able to look at it for you if you want to pay for the service

I would definately try the psu first tough, because a replacement of the full mobo, without looking for some second hand one, would require and almost full system upgrade

EDIT: sorry for the long post