|I don't know why you would change video cards to fix a power problem?|
Did you blow the dust out of your case? Did you confirm that the fans are working, especially the CPU cooling fan? Some boards have a sensor that detects whether the CPU fan is working or not...if it's not detected, the system will automatically shutdown to prevent the CPU from burning out.
As for the power supply, you didn't supply any details about the stock eMachines unit (probably a Bestec?) or any of the other ones that you tried. It's difficult to help if you don't supply all the details.